1.Codeforces 961F k-substrings

Main idea: given a string, for all its substrings    K − substrings    k-substrings\;k − substrings, ask its prefix and suffix the same maximum length, and the length must be odd, if not, then it is    1    \; - 1 \; - 1.    K − substrings    k-substrings\;k − substrings are defined as follows: for each string, delete    i   i\;i characters at the beginning and end of each string.

Design idea: for this problem, we consider using the string     Hash\;Hash to solve. First, consider the simple enumeration idea, that is, for a substring, enumerate all odd prefixes and suffixes from large to small, and then judge whether they are equal according to Hash value. In the worst case, the complexity will reach   O(n2)   O(n^2)\;O(n2), even if   4s   4s\;4s is not enough. Observe the characteristics of strings. When calculating the maximum common prefix and suffix of   I ⁩ i\;i, because each substring shrinks from two ends to the middle, there is such a result as   res[i] − 2 ≤ res[i+1]   res[i]-2 ≤ res[i+1]\;res[i] − 2 ≤ res[i+1], as shown in the following figure:

- 2. res[i+1]+2\;res[i] ≤ res[i+1]+2, the problem is just to find the maximum value. According to this equation, we can get the result + 2 of the longer substring that will not be shorter, so we start enumeration from the middle, and then for each substring, we start from the last result, step by step - 2, to judge whether the Hash value is equal.

Solution:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const ll base = 131;
const ll mod = 1e9 + 7;
ll Hash[maxn], b[maxn];
char ch[maxn];
int n, t, res[maxn / 2];
inline int read()
{
	int t = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		t = (t << 3) + (t << 1) + (ch ^ 48);
		ch = getchar();
	}
	return t;
}
inline void write(int t)
{
	if (t < 0)
	{
		putchar('-');
		t = -t;
	}
	if (t > 9)
	{
		write(t / 10);
	}
	putchar(t % 10 + '0');
}
inline void init()
{
	b[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		b[i] = (b[i - 1] * base) % mod;
	}
	for (int i = 1; i <= n; i++)
	{
		Hash[i] = (Hash[i - 1] * base + ch[i] - 'a' + 1) % mod;
	}
}
inline ll get_hash(int l, int r)
{
	return ((Hash[r] - Hash[l - 1] * b[r - l + 1]) % mod + mod) % mod;
}
inline void solve(int x)
{
	int y = t + t - x;
	if (!(n & 1))		//It's still a parity problem. When the number is even, the right boundary is + 1. You can find it by simple simulation
	{
		y++;
	}
	for (int i = res[x + 1] + 2; i >= 1; i -= 2)		//Enumeration from last result
	{
		if (get_hash(x, x + i - 1) == get_hash(y - i + 1, y))
		{
			res[x] = i;
			return;
		}
	}
	res[x] = -1;
	return;
}
int main()
{
	n = read();
	scanf("%s", ch + 1);
	init();
	t = n / 2;			//Deal with odd and even string length respectively
	if (n & 1)
	{
		t++;
		res[t] = -1;		//For an odd length string, the length at both ends is symmetric with respect to a character. The characters in the middle must have no prefix or suffix
	}
	else
	{
		if (ch[t] == ch[t + 1])		//Even length can be compared with the middle two characters
		{
			res[t] = 1;
		}
		else
		{
			res[t] = -1;
		}
	}
	for (int i = t - 1; i > 0; i--)
	{
		solve(i);		//Start enumeration from the middle, and then solve the longer substring
	}
	for (int i = 1; i <= t; i++)
	{
		write(res[i]);
		if (i == t)
		{
			putchar(10);
		}
		else
		{
			putchar(' ');
		}
	}
	return 0;
}

2.Codeforces 985F Isomorphic Strings

Main idea: given a string, and then every time cut off the equal length of the two strings, ask whether the two strings are isomorphic. (isomorphism is a relationship in which two characters are mapped one by one, that is, they cannot be many to one or one to many.)

Design idea: if we simply adopt the one-to-one mapping method to traverse each query substring, then the complexity will certainly not meet the needs. Because the question here is whether two strings can be isomorphic, and the string   Hash\;Hash \; Hash's idea is to map a string to a unique integer as far as possible, and judge whether two strings are equal by comparing two integers. Here, the relationship between the two strings is not only the corresponding characters are equal, but also to meet the special isomorphic relationship. Therefore, hash \; will not be used for strings at this time; Hash, and for the position of each character   Hash\;Hash \; hash, then determine whether it is isomorphic by the value of     \; Hash\;Hash.

How to understand the position    Hash    Hash\;Hash is the difficulty of this problem. First of all, we need to know that    Hash   Hash function has a similar prefix and property. Each character    Hash   Hash value is based on the result of the previous digit multiplied by the value of base plus the value of the base character. Now consider whether the two strings are isomorphic. Let's take a look at the following example;

For example, for the string    abcabbadbcc    abcabbadbcc \; abcabbadbcc, select its two substrings, such as    bcabb    bcabb\;bcabb and    cdbcc   cdbcc, the naked eye can see that these two strings are isomorphic, so how to use the computer to judge? In this example,    f(b)=c   ,    f(c)=d,f(a)=b  ; f(b)=c\;,\;f(c)=d,f(a)=b\;f(b)=c,f(c)=d,f(a)=b, that is to say, each letter has a corresponding relationship with another. With this idea, we consider mapping the original string to 26 01 strings, each 01 string represents a letter, and the position is that this character is 1 and the rest is 0. Then in the above example, we can convert it to 100100000, 010011000100, 00100001011, 000000001000 That is to say, for   B   b\;b and   C   c\;c. The one-to-one mapping is satisfied, because if the substring is A... A... And... C... C... C... , then the corresponding 01 string is 010... 010... And... 010... 010... 010... , these two strings must not be equal. Therefore, to determine whether the two strings are isomorphic, you only need to get the   Hash\;Hash of each letter of the two strings, and then determine whether there is a one-to-one correspondence between the 26 letters of the two strings.

Solution:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 6;
const ll base = 131;
const ll mod = 1e9 + 7;
int n, m;
char ch[maxn];
int x, y, len;
ll Hash[maxn][30], b[maxn];
inline int read()
{
	int t = 0;
	char ch = getchar();
	while (ch < '0' || ch>'9')
	{
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		t = (t << 3) + (t << 1) + (ch ^ 48);
		ch = getchar();
	}
	return t;
}
inline void init()
{
	b[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		b[i] = (b[i - 1] * base) % mod;
	}
}
inline ll get_hash(int l, int r, int t)
{
	return (((Hash[r][t] - Hash[l - 1][t] * b[r - l + 1])) % mod + mod) % mod;
}
inline bool check()
{
	ll res_a[30], res_b[30];
	for (int i = 1; i <= 26; i++)		//Get 26 Hash values of two string pairs
	{
		res_a[i] = get_hash(x, x + len - 1, i);
		res_b[i] = get_hash(y, y + len - 1, i);
	}
	//Sort for comparison
	sort(res_a + 1, res_a + 27);
	sort(res_b + 1, res_b + 27);
	for (int i = 1; i <= 26; i++)
	{
		if (res_a[i] != res_b[i])
		{
			return false;
		}
	}
	return true;
}
int main()
{
	n = read();
	m = read();
	scanf("%s", ch + 1);
	init();
	//Convert the original string to 26 01 strings
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= 26; j++)
		{
			Hash[i][j] = (Hash[i - 1][j] * base % mod + (ll)(ch[i] == (j - 1 + 'a'))) % mod;
		}
	}
	while (m--)
	{
		x = read();
		y = read();
		len = read();
		if (check())
		{
			puts("YES");
		}
		else
		{
			puts("NO");
		}
	}
	return 0;
}

Have time to update the end of the flower!