[KMP]hdoj 3336：Count the string

大致题意：
    给出一个字符串，求出这个字符串的每个前缀在整个串中各出现了多少次。

 

大致思路：
    KMP小小变形，要深刻理解next数组的含义。

 

#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
using namespace std;
const int nMax=200005;
char pat[nMax];
int lenp,next[nMax];

void get_next(){
    int i,j=-1;
    next[0]=-1;
    for(i=1;i<=lenp;i++){
        while(j>-1&&pat[j+1]!=pat[i])j=next[j];
        if(pat[j+1]==pat[i])j++;
        next[i]=j;
    }
}

int main(){
    int cas,ans,i;
    scanf("%d",&cas);
    while(cas--){
        ans=0;
        scanf("%d",&lenp);
        scanf("%s",pat);
        get_next();
        //int j=next[lenp-1];
        for(i=0;i<lenp;i++){
            int j=i;
            while(j!=-1){
                ans++;
                j=next[j];
            }
        }
        printf("%d\n",ans%10007);
    }
    return 0;
}

 

评论

2 楼 暴风雪 2012-04-03  

笔良文昌 写道

    next数组的意义其实就是
    模式串 pat[0..i]上
    pat[0..next[i]] == pat[i-next[i]...i]
    使 strlen(pat[0..next[i]])最大。

参见matrix67大牛神文

1 楼 笔良文昌 2012-04-03  

    next数组的意义其实就是
    模式串 pat[0..i]上
    pat[0..next[i]] == pat[i-next[i]...i]
    使 strlen(pat[0..next[i]])最大。