POJ 2406 Power Strings KMP 或者后缀数组_ACMer_AK的博客

找最小循环节

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;

char B[1000010];
int nex[1100000];
int lenB;
void getNex(){
    lenB = strlen(B);
    nex[0] = -1;
    int i = 0,j = -1;
    while(i < lenB){
        if(j == -1 || B[i] == B[j]){
            ++j,++i;
            if(B[i]!=B[j]){
                nex[i] = j;
            }
            else{
                nex[i] = nex[j];
            }
        }
        else{
            j = nex[j];
        }
    }
}
int main(){
    int n;
    while(scanf("%s",B)){
        if(!strcmp(B,".")) break;
        getNex();
        if(lenB%(lenB-nex[lenB])==0){
            printf("%d\n",lenB/(lenB-nex[lenB]));
        }
        else puts("1");
    }
    return 0;
}
#include <iostream>
#include <algo