KMP入门 vjudge 扩展解法（字符串HASH）

这些简单的KMP题目，都可以用字符串hash求解。下面都是我自己写的解法代码，大家可以看看有没有新的思路。

A

#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int nn=100005;
const int p=131;
string s1,s2;
ull H1[nn*2],H2[nn];
void getH(ull *H,int n,string s){H[0]=0;for(int i=1;i<=n;i++){if(s[i-1]>='a'&&s[i-1]<='z')H[i]=H[i-1]*p+(s[i-1]-'a'+1);elseH[i]=H[i-1]*p+(s[i-1]-'A'+1);}
}
ull qpow(int p,int l){ull res=1,base=p;while(l){if(l&1){res*=base;}base*=base;l>>=1;}return res;
}
int main(){while(cin>>s1>>s2){s1=s1+s1;int l1=s1.length(),l2=s2.length();getH(H1,l1,s1);getH(H2,l2,s2);int i;for(i=0;i<=l1-l2;i++){ull temp=H1[i+l2]-H1[i]*qpow(p,l2);if(temp==H2[l2]){cout<<"yes"<<endl;break;}}if(i==l1-l2+1){cout<<"no"<<endl;}}return 0;
} 

B

#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int nn=1000005;
const int nnn=10005;
const int p=131;
int a[nn],b[nnn];
ull H1[nn*2],H2[nn];
void getH(ull *H,int n,int *s){H[0]=0;for(int i=1;i<=n;i++){H[i]=H[i-1]*p+(s[i-1]+nn);}
}
ull qpow(int p,int l){ull res=1,base=p;while(l){if(l&1){res*=base;}base*=base;l>>=1;}return res;
}
int main(){int t;std::ios::sync_with_stdio(false);cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<m;i++){cin>>b[i];}getH(H1,n,a);getH(H2,m,b);int i;for(i=0;i<=n-m;i++){ull temp=H1[i+m]-H1[i]*qpow(p,m);if(temp==H2[m]){cout<<(i+1)<<endl;break;}}if(i==n-m+1){cout<<-1<<endl;}}return 0;
} 

C

#include<iostream>
#include<string.h>
using namespace std;
typedef unsigned long long ull;
const int nn=50005;
const int p=131;
string s1,s2;
ull H1[nn],H2[nn];
void getH(ull *H,int n,string s){H[0]=0;for(int i=1;i<=n;i++){H[i]=H[i-1]*p+(s[i-1]-'a'+1);}
}
ull qpow(int p,int l){ull res=1,base=p;while(l){if(l&1){res*=base;}base*=base;l>>=1;}return res;
}
int main(){std::ios::sync_with_stdio(false);while(cin>>s1>>s2){int l1=s1.length(),l2=s2.length();getH(H1,l1,s1);getH(H2,l2,s2);int i,ans=0;int n=l1<l2?l1:l2;for(i=1;i<=n;i++){ull temp1=H1[i];ull temp2=H2[l2]-H2[l2-i]*qpow(p,i);if(temp1==temp2){ans=i;}}if(!ans){cout<<0<<endl;}else{cout<<s1.substr(0,ans)<<" "<<ans<<endl;}}return 0;
} 

D

#include<iostream>
#include<string.h>
using namespace std;
typedef unsigned long long ull;
const int nn=100005;
const int p=131;
string s;
ull H[nn];
void getH(ull *H,int n,string s){H[0]=0;for(int i=1;i<=n;i++){H[i]=H[i-1]*p+(s[i-1]-'a'+1);}
}
ull qpow(int p,int l){ull res=1,base=p;while(l){if(l&1){res*=base;}base*=base;l>>=1;}return res;
}
int main(){std::ios::sync_with_stdio(false);int t;cin>>t;while(t--){cin>>s;int l=s.length();getH(H,l,s);int ans=0;for(int i=1;i<l;i++){if(H[i]==H[l]-H[l-i]*qpow(p,i)){ans=i;}}s=s.substr(0,l-ans);int ll=s.length();if(ll==l){cout<<l<<endl;}else if(!(l%ll)){cout<<0<<endl;}else{cout<<ll-l+(l/ll)*ll<<endl;}}return 0;
}

F

#include<iostream>
#include<string.h>
using namespace std;
typedef unsigned long long ull;
const int nn=1005;
const int p=31;
string s1,s2;
ull H1[nn],H2[nn];
void getH(ull *H,int n,string s){H[0]=0;for(int i=1;i<=n;i++){H[i]=H[i-1]*p+(s[i-1]-'a'+1);}
}
ull qpow(int p,int l){ull res=1,base=p;while(l){if(l&1){res*=base;}base*=base;l>>=1;}return res;
}
int main(){std::ios::sync_with_stdio(false);while(cin>>s1){if(s1!="#")cin>>s2;elsebreak;int l1=s1.length(),l2=s2.length();getH(H1,l1,s1);getH(H2,l2,s2);int cnt=0;for(int i=0;i<=l1;i+=l2){if(H2[l2]==H1[i+l2]-H1[i]*qpow(p,l2)){cnt++;}}cout<<cnt<<endl;}return 0;
}