#kmp#poj 1961 period

題目

求字元串 S S S的字首 S [ 1... i ] S[1...i] S[1...i]是否存在循環次數超過 1 1 1的循環節，如果有輸出位置以及最大循環次數

分析

既然說到kmp，那麼就很容易想到 f a i l fail fail數組( n e x t next next數組)，它表示以 i i i結尾的非字首子串與 S S S的字首能夠比對的最長長度，是以 S [ 1... f a i l [ i ] ] = S [ i − f a i l [ i ] + 1... i ] S[1...fail[i]]=S[i-fail[i]+1...i] S[1...fail[i]]=S[i−fail[i]+1...i]

是以當 i − f a i l [ i ] ∣ i i-fail[i]|i i−fail[i]∣i，那麼 S [ 1... i − f a i l [ i ] ] S[1...i-fail[i]] S[1...i−fail[i]]就是 S [ 1... i ] S[1...i] S[1...i]的最小循環節，是以如果 i − f a i l [ f a i l [ i ] ] ∣ i i-fail[fail[i]]|i i−fail[fail[i]]∣i，那麼 S [ 1... i − f a i l [ f a i l [ i ] ] ] S[1...i-fail[fail[i]]] S[1...i−fail[fail[i]]]就是 S [ 1... i ] S[1...i] S[1...i]的最小循環節，以此類推就可以找到答案

代碼

#include <cstdio>
using namespace std;
char s[1000001]; int n,cnt,fail[1000001],j;
int in(){
	int ans=0; char c=getchar();
	while (c<48||c>57) c=getchar();
	while (c>47&&c<58) ans=ans*10+c-48,c=getchar();
	return ans;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
int main(){
    while (n=in()){
    	printf("Test case #"); print(++cnt); putchar('\n');
        for (int i=1;i<=n;i++) s[i]=getchar();
        fail[1]=j=0;
        for (int i=2;i<=n;i++){
        	while (j&&s[i]!=s[j+1]) j=fail[j];//擴充失敗
        	fail[i]=(j+=(s[i]==s[j+1]));//能夠擴充成功
        }
        for (int i=2;i<=n;i++)
        	if (i%(i-fail[i])==0&&i/(i-fail[i])>1) //循環節且循環節不是隻有1個
			    print(i),putchar(' '),
				print(i/(i-fail[i])),putchar('\n');
		putchar('\n');
    }
    return 0;
}