int nxt[1000 * 2 + 1 + 5];
void getNxt(const string &s)
{
nxt[0] = 0;
for (int i = 1; i < s.length(); i++)
{
int j = nxt[i - 1];
while (j != 0 && s[j] != s[i])
j = nxt[j - 1];
if (s[j] == s[i])
j++;
nxt[i] = j;
}
}
// s 与 s 的每一个后缀的 LCP 长度数组 z。
int z[MAXLEN + 5];
void getZ(const string &s)
{
int l, r; // s[l]~s[r] 与 s 开头 r-l+1 个字符相同
l = -1, r = -1;
z[0] = 0;
for (int i = 1; i < s.length(); i++)
{
z[i] = 0;
if (l <= i && i <= r)
// s[0]~s[r-l] == s[l]~s[r]
// s[i-l] == s[i]
// s[i-l]~s[r-l] == s[i]~s[r]
// z[i-l]: s[i-l] 开始的 z[i-l] 这么多个字符和开头的这么多个字符相同
z[i] = min(z[i - l], r - i + 1);
// i开始已有 z[i] 长度与开头相等
// 如果 i 开始的第 z[i]+1 个位置
// 与开头开始的第 z[i]+1 个位置相等z[i]就可以多一个长度
while (i + z[i] < s.length() &&
z[i] < s.length() &&
s[i + z[i]] == s[0 + z[i]])
z[i]++;
// s[i] 开始的 z[i] 个字符,与开头的 z[i] 个字符相等
// s[i]~s[i+z[i]-1]
if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
z[0] = s.length();
}
// b 与 a 的每一个后缀的 LCP 长度数组 zz。
int zz[MAXLEN + 5];
void getZZ(const string &a, const string &b)
{
// z[i] : b[0]~ 与 b[i]~ 的 lcp
getZ(b);
// zz[i] : b[0]~ 与 a[i]~ 的 lcp
int l, r; // b[0] ~ b[r-l] == a[l] ~ a[r]
l = -1, r = -1;
for (int i = 0; i < a.length(); i++)
{
zz[i] = 0;
if (l <= i && i <= r)
// b[0]~s[r-l] == a[l]~a[r]
// b[i-l] == a[i]
// 1: b[i-l]~s[r-l] == a[i]~a[r]
// 2: b[i-l] 开始的 z[i-l] 个字符与 b 开头的 z[i - l] 个字符相等
// 由 1,2 可得 zz[i] 可以以 z[i-l] 作为基础
zz[i] = min(z[i - l], r - i + 1);
// a[i] 开始已有 zz[i] 长度与 b 开头相等
// 如果 a[i] 开始的第 zz[i]+1 个位置
// 与 b[0] 开始的第 zz[i]+1 个位置相等
// 那么 z[i]就可以多一个长度
while (i + zz[i] < a.length() &&
zz[i] < b.length() &&
a[i + zz[i]] == b[0 + zz[i]])
zz[i]++;
// s[i] 开始的 z[i] 个字符,与开头的 z[i] 个字符相等
// s[i]~s[i+z[i]-1]
if (i + zz[i] - 1 > r)
l = i, r = i + zz[i] - 1;
}
}