[KMP]hdoj 2087:カッティング布
大体の意味: パターンの列とテキストの列を指定します.このモードが文字列の中で上書きの出現がないことを求めます.
大体の考え: ベースのKMPに、一つのlast制限を加えます.
大体の考え: ベースの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
",KMP());
}
return 0;
}