目录
字符串hash进阶
字符串hash是指将一个字符串S映射为一个整数，使得该整数可以尽可能唯一地代表字符串S。那么在一定程度上，如果两个字符串转换成的整数相等，就可以认为这两个字符串相同。
针对字符串hash可以采用下面的式子：
其中str[i]表示字符串的i号位，index函数将A~Z转换为0~25。在这个转换方式中，虽然字符串与整数是一一对应的，但是由于没有进行适当处理，因此当字符串长度较长时，产生的整数会非常大，没办法用一般的数据类型保存。为了应对这种情况，只能舍弃一些“唯一性”，将产生的结果对一个整数mod取模。
通过这种方式可以把字符串转换成范围上能接受的整数。但这又会产生另外的问题，也就是可能有多个字符串的hash值相同，导致冲突。不过幸运的是，在实践中发现，在int数据范围内，如果把进制设置为一个级别的素数p（例如10000019），同时把mod设置为一个
级别的素数（例如1000000007），那么冲突的概率将会变得非常小，很难发生冲突。
例题：给出N个只有小写字母的字符串，求其中不同的字符串的个数。
对这个问题，如果只用字符串hash来做，那么只需要将N个字符串使用字符串hash函数转换为N个整数，然后将它们排序去重即可。
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int MOD=1000000007;
const int p=10000019;
vector<int> ans;
long long hashFunc(string str){
long long H=0;
for(int i=0;i<str.length();i++){
H=(H*p+str[i]-'a')%MOD;
}
return H;
}
int main(){
string str;
while(getline(cin,str),str!="#"){
long long id=hashFunc(str);
ans.push_back(id);
}
sort(ans.begin(),ans.end());
int count=0;
for(int i=0;i<ans.size();i++){
if(i==0||ans[i]!=ans[i-1]){
count++;
}
}
cout<<count<<endl;
return 0;
}接着考虑求解字符串的子串的hash值，也就是求解H[i…j].经过一系列推导可以得出hash函数如下
然后来看一个问题：输入两个长度均不超过1000的字符串，求他们的最长公共子串的长度。
对这个问题，可以先分别对两个字符串求出hash值（同时记录对应的长度），然后找出两堆子串对应的hash值中相等的那些，便可以找出最大长度，时间复杂度为，其中n和m分别为两个字符串的长度。
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL MOD=1000000007;
const LL P=100000019;
const LL maxn=1010;
LL powP[maxn],H1[maxn]={0},H2[maxn]={0};
vector<pair<int,int> > pr1,pr2;
void init(int len){
powP[0]=1;
for(int i=1;i<=len;i++){
powP[i]=(powP[i-1]*P)%MOD;
}
}
void calH(LL H[],string &str){
H[0]=str[0];
for(int i=1;i<str.length();i++){
H[i]=(H[i-1]*P+str[i])%MOD;
}
}
int calSingleSubH(LL H[],int i,int j){
if(i==0){
return H[j];
}
return ((H[j]-H[i-j]*powP[j-i+1])%MOD+MOD)%MOD;
}
void calSubH(LL H[],int len,vector< pair<int,int> > &pr){
for(int i=0;i<len;i++){
for(int j=0;j<len;j++){
int hashValue=calSingleSubH(H,i,j);
pr.push_back(make_pair(hashValue,j-i+1));
}
}
}
int getMax(){
int ans=0;
for(int i=0;i<pr1.size();i++){
for(int j=0;j<pr2.size();j++){
if(pr1[i].first==pr2[j].first){
ans=max(ans,pr1[i].second);
}
}
}
return ans;
}
int main(){
string str1,str2;
getline(cin,str1);
getline(cin,str2);
init(max(str1.length(),str2.length()));
calH(H1,str1);
calH(H2,str2);
calSubH(H1,str1.length(),pr1);
calSubH(H2,str2.length(),pr2);
printf("ans=%d\n",getMax());
return 0;
}现在考虑解决最长回文子串问题，这里将用字符串hash+二分的思路去解决它，时间复杂度为。
对一个给定的字符串str，可以先求出其字符串hash数组H1，然后再将str反转，求出反转字符串rstr的hash数组H2，接着分回文串的奇偶情况进行讨论。
（1）回文串的长度为奇数：枚举回文中心点i，二分子串的半径k，找到最大的使子串[i-k,i+k]是回文串的k。其中判断子串[i-k,i+k]是回文串等价于判断str的两个子串[i-k,i]与[i,i+k]是否是相反的串。而这等价于判断str的[i-k,i]子串与反转子串rstr的[len-1-(i+k),len-1-i]子串是否相同（[a,b]在反转字符串中的位置为[len-1-b,len-1-a])，因此只需要判断H1[i-k…i]与H2[len-1-(i+k)…len-1-i]是否相等即可
（2）回文串的长度为偶数：枚举回文空隙点，令i表示空隙左边第一个元素的下标，二分字串的半径为k，找到最大的使子串[i-k+1,i+k]是回文串的k。其中判断子串[i-k+1,i+k]是回文串等价于判断str的两个子串[i-k+1,i]与[i+1,i+k]是否是相反的串。而这等价于判断str的[i-k+1,i]子串与反转字符串rstr的[len-1-(i+k),len-1-(i+1)]子串是否相同，因此只需要判断H1[i-k+1…i]与H2[len-1-(i+k)…len-1-(i+1)]是否相等即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL MOD=1000000007;
const LL P=10000019;
const LL maxn=200010;
LL powP[maxn],H1[maxn],H2[maxn];
void init(){
powP[0]=1;
for(int i=1;i<maxn;i++){
powP[i]=(powP[i-1]*P)%MOD;
}
}
void calH(LL H[],string &str){
H[0]=str[0];
for(int i=1;i<str.length();i++){
H[i]=(H[i-1]*P+str[i])%MOD;
}
}
int calSingleSubH(LL H[],int i,int j){
if(i==0){
return H[j];
}
return ((H[j]-H[i-1]*powP[j-i+1])%MOD+MOD)%MOD;
}
int binarySearch(int l,int r,int len,int i,int isEven){
while(l<r){
int mid=(l+r)/2;
int H1L=i-mid+isEven,H1R=i;
int H2L=len-1-(i+mid),H2R=len-1-(i+isEven);
int hashL=calSingleSubH(H1,H1L,H1R);
int hashR=calSingleSubH(H2,H2L,H2R);
if(hashL!=hashR){
r=mid;
}
else{
l=mid+1;
}
}
return l-1;
}
int main(){
init();
string str;
getline(cin,str);
calH(H1,str);
reverse(str.begin(),str.end());
calH(H2,str);
int ans=0;
//奇回文
for(int i=0;i<str.length();i++){
int maxLen=min(i,(int)str.length()-1-i)+1;
int k=binarySearch(0,maxLen,str.length(),i,0);
ans=max(ans,k*2+1);
}
//偶回文
for(int i=0;i<str.length();i++){
int maxLen=min(i+1,(int)str.length()-1-i)+1;
int k=binarySearch(0,maxLen,str.length(),i,1);
ans=max(ans,k*2);
}
cout<<ans<<endl;
return 0;
}KMP算法
主要解决的是字符串的匹配问题，如果给定两个字符串text和pattern，需要判断字符串pattern是否是字符串pattern是否是字符串text的子串。
next数组
next[i]表示使子串s[0……i]的前缀s[0……k]等于后缀s[i-k……i]的最大的k（前缀和后缀可以重叠，但不能是s[0……i]本身，next[i]就是所求最长相等前后缀中前缀最后一位的下标。求解next数组的过程其实就是模式串pattern自我匹配的过程。
void getNext(char s[],int len){
int j=-1;
next[0]=-1;
for(int i=1;i<len;i++){
while(j!=-1&&s[i]!=s[j+1]){
j=next[j];
}
if(s[i]==s[j+1]){
j++;
}
next[i]=j;
}
}KMP算法
KMP算法的一般思路：
（1）初始化j=-1,表示pattern当前已被匹配的最后位。
（2）让i遍历文本串text，对每个i，执行（3）（4）来试图匹配text[i]和pattern[j+1]。
（3）不断令j=next[j]，直到j回退为-1，或是text[i]=pattern[j+1]成立。
（4）如果text[i]==pattern[j+1]，则令j++。如果j达到m-1，说明pattern是text的子串，返回true。
//KMP算法，判断pattern是否是text的子串
bool KMP(char text[],char pattern[]){
int n=strlen(text),m=strlen(pattern);
getNext(pattern,m);
int j=-1;
for(int i=0;i<n;i++){
while(j!=-1&&text[i]!=pattern[j+1]){
j=next[j];
}
if(next[i]==pattern[j+1]){
j++;
}
if(j==m-1){
return true;
}
}
return false;
} 统计模式串pattern出现次数的KMP算法代码如下：
int KMP(char text[],char pattern[]){
int n=strlen(text),m=strlen(pattern);
getNext(pattern,m);
int ans=0,j=-1;
for(int i=0;i<n;i++){
while(j!=-1&&text[i]!=pattern[j+1]){
j=next[j];
}
if(text[i]==pattern[j+1]){
j++;
}
if(j==m-1){
ans++;
j=next[j];//让j回退到next[j]继续匹配
}
}
return ans;
}KMP算法优化
可以使用nextval数组进行优化，nextval[i]的含义可以理解为当模式串pattern的i+1位发生失配时，i应回退到的最佳位置。求解nextval数组的代码如下：
void getNextval(char s[],int len){
int j=-1;
nextval[0]=-1;
for(int i=1;i<len;i++){
while(j!=-1&&s[i]!=s[j+1]){
j=nextval[j];
}
if(s[i]==s[j+1]){
j++;
}
if(j==-1||s[i+1]!=s[j+1]){
nextval[i]=j;
}
else{
nextval[i]=nextval[j];
}
}
}
