HDU - 2087-减花布条(裸KMP模板)

个人博客

题目链接

题意：

中文题面，题意也说得非常清楚了，给一个文本串，求文本串中有多少个不重复的模式串

题解：

kmp标准做法，甚至基本没有变动。 判断的时候，每当完整的匹配一次之后令j=0，ans++，即模式串的下标从0开始，匹配数量加1

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
using namespace std;
const int maxn=1000030;
int next1[10030];
char s[maxn];
char p[10030];
int cnt=0;
void prefix_next(){
	next1[0]=0;
	next1[1]=0; 
	int j;
	for(int i=1;p[i]!='\0';i++){
        j = next1[i];   
        while(j && p[j] != p[i]) j = next1[j];  
        next1[i+1] = p[j] == p[i] ? j + 1: 0;  		
	}
	return;
}
void kmp(){
	int j=0,m=strlen(p),n=strlen(s);
	for(int i=0;s[i]!='\0';i++){
		while(j && p[j] != s[i]) j = next1[j];  
        if(p[j] == s[i]) j ++;  
        if(j == m) {
        	cnt++;
        	if(i+m<n)
        		j=0;
        	else
        		return;
		}
	}
	return;
}
int main(){
/* #ifdef LOCAL freopen("C:/Users/Administrator/Desktop/input.txt","r",stdin); #endif*/
	while(~scanf("%s",s),strcmp(s,"#")){
		cnt=0;
		cin>>p;
		prefix_next();
		kmp();
		cout<<cnt<<endl;
	}
}