Cyclic Nacklace - HDU 3746(next求循環節)

題目大意：給你一些串，問如果想讓這個串里面的循環節至少循環兩次，需要添加幾個字符（只能在最前面或者最后面添加）。比如ababc 需要添加5個就是添加ababc。

?

分析：其實字符串的長度len-next[len] = 最小循環節長度，為什么？其實也是需要對next的深刻了解，首先我們都知道next是求的最大的前綴和后綴的匹配度比如下面的字符串

ABCABCABC，很直接的就可以看出來最大的匹配串是ABCABC，但怎么從這個看出來最小的循環節呢？我們看到這個串的后綴串是從第4個字符開始的，也就是說從第四個字符開始到最后一直都是有匹配的，如下：

s[4] = s[1]

s[5] = s[2]

s[6] = s[3]

s[7] = s[4] !!!!

看到了什么s[7] = s[4] = s[1]，其實這已經進入了循環，也就是后綴串前面的就是最小的循環節，如果還不明白可以自己在紙上比劃比劃。那么這道題懂了怎么求循環節想必大家也就會做了吧。

下面是AC代碼

==========================================================================================================

#include<stdio.h>
#include<string.h>const int MAXN = 1e5+7;char s[MAXN];
int next[MAXN];void GetNext(char s[], int next[], int N)
{int i=0, j=-1;next[0] = -1;while(i<N){if(j==-1 || s[i]==s[j])next[++i] = ++j;elsej = next[j];}
}int main()
{int T;scanf("%d", &T);while(T--){scanf("%s", s);int N = strlen(s);GetNext(s, next, N);int cyclic = N-next[N], ans=0;if(cyclic == N)ans = N;else if(N % cyclic != 0)ans = cyclic-N%cyclic;printf("%d\n", ans);}return 0;
}

?