题意：
找A串在B串中的出现次数（可重叠），可用KMP做，这里只提供哈希算法做的方法
题解：
先得到A串的hash值，然后在B中枚举起点，长度为lena的子串，检验hash值是否相同就可以了。
代码：
/*
-1 在ull里相当于2的六四次-2
ull炸了就当mod2e64
*/#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef unsigned long long ull;
const int blo=31;
const int maxn = 1e6+5;
ull xp[maxn],hash_1[maxn],hash_2[maxn];
void init()
{
xp[0]=1;
for(int i=1; i<maxn; i++)
xp[i]=xp[i-1]*blo;
}
ull get_hash(int i,int L,ull hash_[])//get_hash(i,L)可以得到从位置i开始的,长度为L的子串的hash值.
{
return hash_[i]-hash_[i+L]*xp[L];
}
int make_hash(char str[],ull hash_[])
{
int len=strlen(str);
hash_[len]=0;
for(int i=len-1; i>=0; i--)
{
hash_[i]=hash_[i+1]*blo+(str[i]-'A'+1);
//cout<<hash_[i]<<" ";
}
return len;
}
char str[maxn],str2[maxn];
int main()
{ init();
//printf("%d\n",31644418079342855-13357*xp[3]);
int t;
scanf("%d",&t);
while(t--)
{
int ans=0;
scanf("%s%s",str,str2);
int len1=make_hash(str,hash_1);
int len2=make_hash(str2,hash_2);
//printf("\n");
ull tmp=get_hash(0,len1,hash_1);
//cout<<tmp<<"****"<<xp[len1]<<endl;
for(int i=0; i<len2-len1+1; i++) //注意枚举时的边界问题
{
if(get_hash(i,len1,hash_2)==tmp)
ans++;
}
printf("%d\n",ans);
}
return 0;
}
题意：
求两个串的最长公共子串，另一种解法是后缀数组，这里只讲哈希算法求解过程
题解：
由于没有给定长度，要求长度，这时就要想是否具有二分的性质，发现答案是具有二分性质的，所以我们可以二分答案，然后把A串中所有出现过的hash值放进一个数组，sort一下，然后对于每个B串产生的hash用lower_bound查询是否出现过，若出现过则直接返回true.复杂度是o(len*log(len)*log(len))o(len∗log(len)∗log(len))。不能使用map，因为map的复杂度要多一个log
代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;
const int maxn=1e6+10;
const int blo=31;
typedef unsigned long long ull;
ull xp[maxn],hash_1[maxn],hash_2[maxn];
ull a[maxn];
int len1,len2;
void init()
{
xp[0]=1;
for(int i=1;i<maxn;++i)
{
xp[i]=xp[i-1]*blo;
}
}
ull Get_hash(int i,int len,ull hash_[])
{
return hash_[i]-hash_[i+len]*xp[len];
}
int Make_hash(char s[],ull hash_[])
{
int len=strlen(s);
hash_[len]=0;
for(int i=len-1;i>=0;--i)
{
hash_[i]=hash_[i+1]*blo+(s[i]-'A'+1);
}
return len;
}
char s1[maxn],s2[maxn];
int check(int x)
{
int cnt=0;
for(int i=0;i<len1-x+1;i++)
{
a[cnt++]=Get_hash(i,x,hash_1);
}
sort(a,a+cnt);
for(int i=0;i<len2-x+1;++i)
{
ull tmp=Get_hash(i,x,hash_2);
int pos=lower_bound(a,a+cnt,tmp)-a;
if(a[pos]==tmp) return 1;
}
return 0;
}
int main()
{
init();
while(~scanf("%s%s",s1,s2))
{
len1=Make_hash(s1,hash_1);
len2=Make_hash(s2,hash_2);
int l=0,r=min(len1,len2),mid,ans=0;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
printf("%d\n",ans);
}
return 0;
}
题意：
求字符串中至少出现过k次的最长子串。
题解：
这道题哈希做法和上一道题很相似，你只需要确定一个这个串的出现次数大于等于k，那么可以在用一个upper_bound()函数和一个lower_bound()来确定这个子串在主串中的出现次数
代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;
const int maxn=2e4+10;
const int blo=31;
typedef unsigned long long ull;
ull xp[maxn],hash_1[maxn];
ull a[maxn];
int n,k;
void init()
{
xp[0]=1;
for(int i=1;i<maxn;++i)
{
xp[i]=xp[i-1]*blo;
}
}
ull Get_hash(int i,int len,ull hash_[])
{
return hash_[i]-hash_[i+len]*xp[len];
}
void Make_hash(ull s[],ull hash_[])
{
hash_[n]=0;
for(int i=n-1;i>=0;--i)
{
hash_[i]=hash_[i+1]*blo+s[i];
}
//return len;
}
ull s[maxn];
int check(int x)
{
int cnt=0;
for(int i=0;i<n-x+1;i++)
{
a[cnt++]=Get_hash(i,x,hash_1);
}
sort(a,a+cnt);
for(int i=0;i<n-x+1;++i)
{
ull tmp=Get_hash(i,x,hash_1);
int pos=lower_bound(a,a+cnt,tmp)-a;
if(a[pos]==tmp)
{
int index=upper_bound(a,a+cnt,tmp)-a;
//printf("%d %d %d %d\n",pos,index,i,x);
if(index-pos>=k) //这里是大于等于号
return 1;
//else return 0;
}
}
return 0;
}
int main()
{ init();
while(~scanf("%d%d",&n,&k))
{
for(int i=0;i<n;++i)
scanf("%llu",&s[i]);
Make_hash(s,hash_1);
int l=0,r=n,mid,ans=0;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
printf("%d\n",ans);
}
return 0;
}
