[KMP]hdoj 2087：剪花布条

大致题意：
    给出一个模式串，一个文本串。求这个模式串在文本串中无覆盖的出现了多少次。

 

大致思路：
    基础KMP，加上一个last限制。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=10005;
const int mMax=1000005;
char text[mMax],pat[nMax];
int lent,lenp,next[nMax];

void get_next(){
    int i,j=-1;
    next[0]=-1;
    for(i=1;i<=lenp;i++){     //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符
        while(j>-1&&pat[j+1]!=pat[i])j=next[j];
        if(pat[j+1]==pat[i])j++;
        next[i]=j;
    }
}

int KMP(){
    int ans=0,i=0,j=-1,last=-lenp-1;;
    get_next();
    for(i=0;i<lent;i++){
        while(j!=-1&&pat[j+1]!=text[i]){
            j=next[j];
        }
        if(pat[j+1]==text[i])j=j+1;
        if(j==lenp-1){
            if(i-last>=lenp){
                ans++;  //找到一个匹配
                last=i;
            }
        }
      //  cout<<i<<endl;
    }
    return ans;
}

int main(){
    int t;
    //scanf("%d",&t);
    while(scanf("%s",text)){
        if(text[0]=='#')break;
        scanf("%s",pat);
        lenp=strlen(pat);
        lent=strlen(text);
        printf("%d\n",KMP());
    }
    return 0;
}

 

评论

2 楼 暴风雪 2012-04-03  

笔良文昌 写道

宇哥，你想多了。
其实我们每次成功匹配后，把j赋值为-1就行了。这样就表示模式串从头开始匹配了。对吧？

嗯，敢于改动模版是好习惯啊Orz

1 楼 笔良文昌 2012-04-02  

宇哥，你想多了。
其实我们每次成功匹配后，把j赋值为-1就行了。这样就表示模式串从头开始匹配了。对吧？