题意

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

思路

哈希/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;
}

#include<bits/stdc++.h>
using namespace std;
string a,b;
int p=131,s=0;
long long pown[1000001];
long long h[1000001];
long long h2[1000001];
int main(){
	cin>>a>>b;
	int len=a.size();
	int len2=b.size();
	pown[0]=1;
	for(int i=1;i<=len;i++){
		pown[i]=pown[i-1]*p;
	}
	for(int i=1;i<=len;i++){
		h[i]=h[i-1]*p+a[i-1];
	}
	for(int i=1;i<=len2;i++){
		h2[i]=h2[i-1]*p+b[i-1];
	}
	for(int i=1;i<=len-len2+1;i++){
		if((h[i+len2-1]-h[i-1]*pown[len2])==h2[len2]){
			s++;
		}
	}
	cout<<s;
} 

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005,BASE = 2617;
int h[N],hb,pown[N] = {1},cnt;
int main(int argc, char **argv){
	for (int i = 1;i < N;i++)	pown[i] = pown[i - 1] * BASE;
	string a,b;
	cin >> a >> b;
	int len1 = a.size(),len2 = b.size();
	for (int i = 0;i < len2;i++){
		hb = hb * BASE + (b[i] - 'A' + 1);
	}
	for (int i = 1;i <= len1;i++){
		int si = i - 1;
		h[i] = h[i - 1] * BASE + (a[si] - 'A' + 1);
	}
	for (int i = 1;i <= len1 - len2 + 1;i++){
		if (h[i + len2 - 1] - h[i - 1] * pown[len2] == hb)	cnt++;
	}
	cout << cnt;
	return 0;
}