KMP算法的一些应用

POJ 2406 Power Strings

题目意思为求一个最小的子串，使原串由 n 个子串连接而成。 假设子串长度为 k, 则对于该字符串有

S[1, len(S)- k]== S[k+ 1, len(S)], 且 k 最小， 也说是 len(S)- k最大，这恰好是 KMP 算法中

的 next[] 数组。求出 next[ len(S) ], 则 len(S)- next[ len(S) ] 为子串的长度。

 

代码：

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

char str[1000001];
int next[1000001];

int main(){
    while( gets(str)!= NULL ){
        if( strcmp( str, "." )== 0 ) return 0;
        
        int i= 0, j= -1; next[0]= -1;
        while( str[i] ){
            if( j== -1 || str[i]== str[j] ){
                i++; j++; next[i]= j;
            }
            else j= next[j];
        }
        int len= i; i-= j;
        if( len% i== 0 ) printf("%d\n", len/ i );
        else printf("1\n");
    }
    
    return 0;
}

HDU 3366 代码：

#include <stdio.h>
#include <stdlib.h>

#define N 200010

char str[N];
int n, next[N], dp[N];

int main(){
    int test;
    scanf("%d",&test );
    while( test-- ){
        scanf("%d",&n );
        scanf("%s", str );
        
        int i= 0, j= -1; next[0]= -1;
        while( str[i] ){
            if( j== -1 || str[i]== str[j] ){
                i++; j++; next[i]= j; }
            else j= next[j];
        }
        next[n]= j;
        
        for( int i= 0; i<= n; ++i ) dp[i]= 1;
        for( int i= n; i> 0; i-- )
        if( next[i]> 0 ) dp[ next[i]- 1]+= dp[i];
        
        int ans= 0;
        for( int i= 0; i< n; ++i )
        ans= ( ans+ dp[i] ) % 10007;
        
        printf("%d\n", ans );
    }
    
    return 0;
}