Period UVA - 1328
题意：
给你一个串。要求你计算每个前缀是否可以由一个循环节，重复k次得到（k>1）
思路：
就是模板题。 后缀函数的定义，“错位部分”长度为
i
−
n
e
x
t
[
i
]
i-next[i]
i−next[i]. 如果这
i
i
i个字符串组成一个周期串，那么“错位”部分恰好就是一个循环节。
条件.
k>1.
k
(
i
−
n
e
x
t
[
i
]
)
=
i
k(i-next[i])=i
k(i−next[i])=i
证明
AC
#include <iostream>
#include <cstring>
#include <string>
using namespace std
;
const int maxn
=1e6+10;
int nxt
[maxn
];
char s
[maxn
];
void getnxt(char *p
){
int m
= strlen(p
);
int i
=0,j
=-1;
nxt
[0]=-1;
while(i
<m
){
if(j
==-1||p
[i
]==p
[j
])nxt
[++i
]=++j
;
else j
=nxt
[j
];
}
}
int main()
{
ios
::sync_with_stdio(0);cin
.tie(0);cout
.tie(0);
int n
,kase
=0;
while(cin
>>n
&&n
){
cin
>>s
;
getnxt(s
);
cout
<<"Test case #"<<++kase
<<endl
;
for(int i
=2; i
<=n
; i
++){
if(nxt
[i
]>0 && i
%(i
-nxt
[i
])==0)cout
<<i
<<' '<<i
/(i
-nxt
[i
])<<endl
;
}
cout
<<endl
;
}
return 0;
}
