传送门:2752 -- Seek the Name, Seek the Fame
题意:给一个字符串s,要求所有最后一个字符结尾的相同前缀和后缀的长度,自身也算
Sample Input
ababcababababcabab aaaaa
Sample Output
2 4 9 18 1 2 3 4 5
样例1解释:
a b a b c a b a b a b a b c a b a b
对于9:
a b a b c a b a b a b a b c a b a b
对于4
a b a b c a b a b a b a b c a b a b
对于2
a b a b c a b a b a b a b c a b a b
思路:一般的kmp处理完每个位置都只会有一个next值,所以这里并不能。但kmp具有一个很强的性质。
证明是应该不对
与字符串——周期(kmp)_北岭山脚鼠鼠的博客-CSDN博客 这个有很大关系。
代码:
- #include
- #include
- #include
- #include
- using namespace std;
- typedef unsigned long long ull;
- const int N=1e6+10;
- char a[N];
- int ne[N];
- int n,m;
- void get()
- {
- ne[1]=0;
- int j=0;
- for(int i=2;i<=n;i++)
- {
- while(j>0&&a[i]!=a[j+1]) j=ne[j];
- if(a[i]==a[j+1]) j++;
- ne[i]=j;
- }
- }
- int main()
- {
- while(cin>>a+1)
- {
- n=strlen(a+1);
- get();
- vector<int>v;
- int j=n;
-
- while(ne[j]!=0)
- {
- v.push_back(ne[j]);
- j=ne[j];
- }
- for(int i=v.size()-1;i>=0;i--)
- cout<
' '; - cout<
- }
- return 0;
- }