题意

求有多少个非空相同的子串个数

思路

哈希/KMP

哈希代码

哈希好写,但性能比KMP差一点

总耗时: 352ms

峰值内存: 9.2 MiB

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
string a,b;


int P=11289;
int p[N];
int ha[N];
int hb[N];
int len(int l,int r)
{
	return ha[r]-ha[l-1]*p[r-l+1];
}
int s_hash()
{
	int sum=0;
	p[0]=1;
	for(int i=1;i<=a.size();i++)
		p[i]=p[i-1]*P;
	for(int i=1;i<=a.size();i++)
		ha[i]=ha[i-1]*P+a[i-1];
	for(int i=1;i<=b.size();i++)
		hb[i]=hb[i-1]*P+b[i-1];
	for(int i=1;i<=a.size()-b.size()+1;i++)
		if(len(i,i+b.size()-1)==hb[b.size()])
			sum++;
	return sum;
}


int main()
{
	cin>>a>>b;
	cout<<s_hash();
	return 0;
}

KMP代码

KMP难写,但性能优

总耗时: 308ms

峰值内存: 2.4 MiB

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
string a,b;


int border[N];
void fb()
{
	int j=0;
	for(int i=1;i<b.size();i++)
	{
		while(j && b[i]!=b[j])j=border[j-1];
		if(b[i]==b[j])j++;
		border[i]=j;
	}
}
int s_kmp()
{
	fb();
	int j=0,sum=0;
	for(int i=0;i<a.size();i++)
	{
		while(j && a[i]!=b[j])j=border[j-1];
		if(a[i]==b[j])j++;
		if(j==b.size())
			sum++,j=border[j-1];
	}
	return sum;
}


int main()
{
	cin>>a>>b;
	cout<<s_kmp();
	return 0;
}