首先求出next数组,可知字符串最长公共前后缀为数组最后一个元素。
将前后缀中的重叠部分拿出来合并比较,我们不难发现最小重复单元就是字符串长度和字符串最长公共前缀和的差值。
例如:
项目 | 内容 |
---|---|
原串 | CABCABCA |
最长公共前缀 | CABCA |
最长公共后缀 | CABCA |
例中重叠部分是CA,而两串所“空缺”的地方正好就是一个完整的重复单元。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000001;
int l;
int len;
int pi[MAXN];
string s;
int main() {
ios::sync_with_stdio(false);
cin >> l >> s;
len = s.length();
int j = 0;
for ( int i = 1; i < len; ++i ) {
j = pi[i - 1];
while ( j && s[j] != s[i] )
j = pi[j - 1];
if ( s[j] == s[i] )
++j;
pi[i] = j;
}
cout << l - pi[l - 1] << endl;
return 0;
}