poj 2406 Power Strings（kmp求一个串的重复子串）

题意：重复子串次数

思路：kmp

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

#define MaxSize 1000005

int next[MaxSize];

void GetNext(char t[]){//求next数组

    int j,k,len;

    j=;

    k=-;

    next[]=-;

    len=strlen(t);

    while(j<len){

        if(k==-||t[j]==t[k]){

            ++j;

            ++k;

            next[j]=k;//此句可由优化替代

            /*优化（仅保证求KMPIndex时可用。谨慎使用。）

            if(t[j]!=t[k])next[j]=k;

            else next[j]=next[k];

            */

        }

        else k=next[k];

    }

}

int KMPIndex(char s[],char t[]){//求子串首次出现在主串中的位置

    int i,j,lens,lent;

    i=j=;

    lens=strlen(s);

    lent=strlen(t);

    while(i<lens&&j<lent){

        if(j==-||s[i]==t[j]){

            ++i;

            ++j;

        }

        else j=next[j];

    }

    if(j>=lent)return i-lent;

    else return -;

}

int KMPCount(char s[],char t[]){//统计子串在主串中的出现次数，可重叠

    int i,j,lens,lent,cnt;

    i=j=;

    lens=strlen(s);

    lent=strlen(t);

    cnt=;

    while(i<lens){

        if(j==-||s[i]==t[j]){

            ++i;

            ++j;

        }

        else j=next[j];

        if(j==lent)++cnt;

    }

    return cnt;

}

void KMPCount2(char t[]){//统计单串中从某个位置以前有多少重复的串

    int i,lent,tmp;

    lent=strlen(t);

    for(i=;i<=lent;++i){

        tmp=i-next[i];

        if(i%tmp==&&i/tmp>)

            printf("\t位置：%d 个数：%d\n",i,i/tmp);

    }

}

int main(){

    char str[MaxSize];

    int len;

    while(~scanf("%s",str)&&str[]!='.'){

        GetNext(str);

        len=strlen(str);

        if(len%(len-next[len])==&&len/(len-next[len])>)printf("%d\n",len/(len-next[len]));

        else printf("1\n");

    }

    return ;

}