for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && (j == n || b[i] != a[j + 1])) j = ne[j];
if (b[i] == a[j + 1]) j ++ ;
f[i] = j;
// if (f[i] == n) //此时就是 A 在 B 中的某一次出现
}
vector<int> ans(n + 1);
for (int i = 1; i <= n; i ++ ) ans[pi[i]]++;
for (int i = n; i >= 1; i -- ) ans[pi[i - 1]] += ans[i];
for (int i = 1; i <= n; i ++ ) ans[i]++;
字符串最小表示法
字符串的最小表示法：最小表示法是求与某个字符串 循环同构 的所有字符串中，字典序最小的
如何在
O(N)
的时间内求出字符串的最小表示
类似 循环同构 的问题，第一时间想到 破环成链，将数组整体复制接到后面，然后寻找长度为
n
的最小字典序
先枚举起点，然后暴力挨个比较的做法，时间复杂度为
O(N^2)
，对于本题的数据规模完全是 ok 的
这里介绍一个线性的做法：
考虑对于一对字符串
A,B
, 它们在原字符串
S
中的起始位置分别为
i,j
, 且它们的前
k
个字符均相同，即
[
A[i \cdots i + k - 1] = B[j \cdots j + k - 1]
]
不妨先考虑
A[i+k] > B[j + k]
的情况，我们发现起始位置下标
l
满足
i \le l \le i + k
的字符串均不能成为答案。因为对于任意一个字符串
S_{i+p}
（表示以
i+p
为起始位置的字符串）一定存在字符串
S_{j+p}
比它更优。
所以我们比较时可以跳过下标
l\in[i,i+k]
, 直接比较
S_{i+k+l}
这样对于每个指针都只会向后位移，因此时间复杂度为
O(N)
算法流程
初始化指针
i
为
1
，
j
为
2
通过直接向后扫描的方法，比较
S[i]
与
S[j]
两个循环同构串
如果扫描了
n
个字符后仍然相等，说明
S
有更小的循环元，且该循环元已扫描完毕，
S[min(i,j) ... min(i,j) + n - 1]
即为最小表示
如果在
i+k
与
j+k
处发现不相等：
若
S[i+k] > S[j+k]
，令
i = i + k + 1
若此时
i=j
，则令
i=i+1
若
S[i+k] < S[j+k]
，令
j = j + k + 1
若此时
i=j
，则令
j=j+1
若
i > n
或
j > n
，则
S[min(i,j) ... min(i,j) + n - 1]
即为最小表示，否则重复第二步
代码语言：javascript
复制
int n = strlen(s + 1);
for (int i = 1; i <= n; i ++ ) s[n + i] = s[i];
int i = 1, j = 2, k;
while (i <= n && j <= n)
{
for (k = 0; k < n && s[i + k] == s[j + k]; k ++ );
if (k == n) break; // 形如catcat，它的循环元已扫描完成
if (s[i + k] > s[j + k])
{
i = i + k + 1;
if (i == j) i ++ ;
}
else
{
j = j + k + 1;
if (i == j) j ++ ;
}
}
ans = min(i, j);
习题
周期
题目描述
一个字符串的前缀是从第一个字符开始的连续若干个字符，例如
abaab
共有
5
个前缀，分别是
a
，
ab
，
aba
，
abaa
，
abaab
。
我们希望知道一个
N
位字符串
S
的前缀是否具有循环节。
换言之，对于每一个从头开始的长度为
i
（
i>1
）的前缀，是否由重复出现的子串
A
组成，即
AAA…A
（
A
重复出现
K
次,
K>1
）。
如果存在，请找出最短的循环节对应的
K
值（也就是这个前缀串的所有可能重复节中，最大的
K
值）。
输入格式
输入包括多组测试数据，每组测试数据包括两行。
第一行输入字符串
S
的长度
N
。
第二行输入字符串
S
。
输入数据以只包括一个
0
的行作为结尾。
输出格式
对于每组测试数据，第一行输出 Test case # 和测试数据的编号。
接下来的每一行，输出具有循环节的前缀的长度
i
和其对应
K
，中间用一个空格隔开。
前缀长度需要升序排列。
在每组测试数据的最后输出一个空行。
数据范围
2≤N≤1000000
输入样例：
代码语言：javascript
复制
3
aaa
4
abcd
12
aabaabaabaab
0
输出样例：
代码语言：javascript
复制
Test case #1
2 2
3 3
Test case #2
Test case #3
2 2
6 2
9 3
12 4
解析
根据我在上文中的有关 “前缀函数求字符串的周期” 内容继续
对于一个字符串border长度，其最长为
|r|_{max} = \pi[n]
，因此最小正周期为
|T|_{min} = n - \pi[n]
综上，如果当前字符串的最小正周期
\pi[i]
能够整除当前字符串的长度
i
，则他一定存在循环元
根据该理论，输出结果即可
代码语言：javascript
复制
void solve()
{
scanf("%s", str + 1);
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && str[i] != str[j + 1]) j = ne[j];
if (str[i] == str[j + 1]) j ++ ;
ne[i] = j;
}
for (int i = 2; i <= n; i ++ )
if (i % (i - ne[i]) == 0 && i / (i - ne[i]) > 1)
printf("%d %d\n", i, i / (i - ne[i]));
puts("");
}
