[hdu] p2087 cut cloth strip

kmp Do not overlap matching template questions . Topic link

In a normal kmp Matching , Overlap matching can occur . If no overlap is required , The following changes should be made ：

void work()
{
    
	int j=0;
	for (int i=1; i<=len1; i++)
	{
    
		while(j && s2[j+1]!=s1[i]) j=p[j];
		if (s2[j+1]==s1[i]) j++;
		if (j==len2)
		{
    
			ans++; 
			j=0;  // It was originally j=p[j];
		}
	}
}

Complete code ：

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn = 1e5+5;

using namespace std;

char s1[maxn],s2[maxn];
int len1,len2,ans;
int p[maxn];

void get()
{
    
	int j=0;
	p[1]=0;
	for (int i=2; i<=len2; i++)
	{
    
		while(j && s2[j+1]!=s2[i]) j=p[j];	
		if (s2[j+1]==s2[i]) j++;
		p[i]=j;
	}
}

void work()
{
    
	ans=0;
	int j=0;
	for (int i=1; i<=len1; i++)
	{
    
		while(j && s2[j+1]!=s1[i]) j=p[j];
		if (s2[j+1]==s1[i]) j++;
		if (j==len2)
		{
    
			ans++;
			j=0;
		}
	}
}

int main()
{
    
   	FAST; 
   	while(cin>>s1+1)
   	{
    
   		if (s1[1]=='#') break;
   		
   		cin>>s2+1;
   		
   		len1=strlen(s1+1);
   		len2=strlen(s2+1);
   		
   		memset(p,0,sizeof(int)*(len2+10));

		get();
		work();
		
		cout<<ans<<endl;	
	}
return 0;
}