程式碼備份區

題意：

給一個字串，輸出他一個區間內重複出現兩次以上相同字串的數字

ex:

aabaabaabaab

aa，有出現兩次 a ，所以要輸出2 2(到第二個為止共兩次a)

aabaab，出現兩次aab，所以輸出6 2(到第六個為止出現兩次aab)

aabaabaab，出現三次aab，所以輸出9 3(到第九個為止出現三次aab)

aabaabaabaab，出現四次aab，所以輸出12 4(到第12個為止出現四次aab)

解法：

做KMP的prefix，如果目前長度減掉prefix長度可以被目前長度整除，表示會有重複連續出現的字串

程式碼：

#include <stdio.h>
#include <string.h>
#include <string.h>

int n;
char str[1000011];
int pre[1000011];

int main(){
    int i,j;
    int Case = 0;
    while(scanf("%d",&n)!=EOF &&n){
        gets(str);
        gets(str);
        printf("Test case #%d\n",++Case);
        for(i=1,pre[0]=j=-1;i<n;++i){
            while(j>=0 && str[j+1]!=str[i]) j=pre[j];
            if(str[j+1]==str[i])++j;
            pre[i] = j;
            if(j>=0 && (i+1)%(i-j)==0){
                printf("%d %d\n",i+1,(i+1)/(i-j));
            }
        }
        puts("");
    }
    return 0;
}