uva_10298

若len%(len-next[len])==0，则最小循环节为len/(len-next[len])

#include <iostream>
#include <string>
#include <cstring>


void computeTemporaryArray();
bool KMP();

int lps[1000007];
char pattern[1000007];
char text[1000007];
int count;
int lengthOfPattern;
int lengthOfStr;


int main(){

    char str[]="aaaa";
    char subString[]="aaaa";


    while(1){
        std::cin.getline(pattern,1000005);

        if(pattern[0]=='.'){
            break;
        }
        //printf("strlen:%lu\n",strlen(pattern));
        //lengthOfStr=sizeof(str)-1;
        lengthOfPattern=std::strlen(pattern);

        computeTemporaryArray();

        printf("%d\n",count);
    }


    //sizeof(subString)-1  == 總包含字元數
    //
    //memcpy(pattern,subString,sizeof(subString));
    //memcpy(text,str,sizeof(str));

    return 0;
}
//計算失敗函數
void computeTemporaryArray(){
                lps[0]=-1;
        int index =0;
        for(int i=1; i <=lengthOfPattern;){
            if(pattern[i] == pattern[index]){
                lps[i+1] = index + 1;
                index++;
                i++;
            }else{
                if(index != 0){
                    index = lps[index];
                }else{
                    lps[i+1] =0;
                    i++;
                }
            }
        }

                printf("%s\n",pattern);
                for(int i=0;i<=lengthOfPattern;i++){
                    printf("%d ",lps[i]);
                }
                printf("\n");
                if((lengthOfPattern%(lengthOfPattern-lps[lengthOfPattern]))==0){
                    count=lengthOfPattern/(lengthOfPattern-lps[lengthOfPattern]);
                }else{
                    count=1;
                }
}

題外話，不使用kmp的暴力解法，比kmp慢

#include <iostream>
#include <string>
#include <cstring>


void computeTemporaryArray();
bool KMP();

char pattern[1000007];
char text[1000007];
int count;
int lengthOfPattern;
int lengthOfStr;


int main(){

    char str[]="aaaa";
    char subString[]="aaaa";


    while(1){
        std::cin.getline(pattern,1000005);

        if(pattern[0]=='.'){
            break;
        }
        //printf("strlen:%lu\n",strlen(pattern));
        //lengthOfStr=sizeof(str)-1;
        lengthOfPattern=std::strlen(pattern);

        computeTemporaryArray();

        printf("%d\n",count);
    }


    //sizeof(subString)-1  == 總包含字元數
    //
    //memcpy(pattern,subString,sizeof(subString));
    //memcpy(text,str,sizeof(str));

    return 0;
}
//計算失敗函數
void computeTemporaryArray(){
        int i =0;
                count=0;//整個pattern match 了幾次
                int match_count=0;//str match 了 pattern 的幾個字元
                int length=1;
        for(int j=1; j < lengthOfPattern;){
                        //printf("for\n");
            if(pattern[j] == pattern[i]){
                                //printf("equal\n");
                i++;
                j++;
                                match_count++;
                                if(match_count==length){
                                    count++;
                                    match_count=0;
                                }
            }else{
                                if(match_count){
                                    length=j+1-match_count;
                                    j=length;
                                    //printf("match_count %d\n",match_count);
                                    count=0;
                                    match_count=0;
                                    i=0;
                                }else{
                                    //printf("not equal\n");

                                    //length++;
                                    length=j+1;

                                    count=0;
                                    match_count=0;
                                    i=0;

                                    //j=length;
                                    j++;
                                }

            }
                        if(j==lengthOfPattern && match_count!=0){
                            count=0;
                        }
                        //printf("match_count:%d\n",match_count);
        }
                count++;
                //printf("length:%d\n",length);
}