前言

字符串哈希通常是用于字符串之间进行各种比较，之前一直没学这个算法，直到wjm学长推的题要用到，我才学了一点。

基本思路

所谓字符串哈希，实际上就是找个方法把字符串映射成可以进行比较的数字。（因为c++里字符串内部无法直接进行比较），当然，因为是映射成数字，而且值域通常无法十分大（否则会爆），所以偶尔会有冲突。一个好的哈希就很重要。

基本上来说就是应用了前缀和的思想，先将字符串中的不同字母都映射成某个不同数字（如对应的 ASCII 值），在用前缀和以及类似进制转换的思路使得可以方便的求出某一段的总和。为了保证在某一值域内，通常要对大质数取模（减少冲突的概率）。

代码实现

我暂时都还是在判断回文的时候用到这个算法。

AcWing 139

#include <bits/stdc++.h>

using namespace std;
const int N=1e6+10;
const int P=131;


char s[N];
unsigned long long h[N],f[N],p[N];
int n,cnt;

unsigned long long query1(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}

unsigned long long query2(int l,int r){
    return f[l]-f[r+1]*p[r-l+1];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    while(cin>>(s+1)&&strcmp(s+1,"END")){
        cnt++;
        int ans=0;
        int n=strlen(s+1);
        p[0]=1;
        for(int i=1;i<=n;i++){
            p[i]=p[i-1]*P;
            h[i]=h[i-1]*P+s[i];
        }
        f[n+1]=0;
        for(int i=n;i>=1;i--){
            f[i]=f[i+1]*P+s[i];
        }
        for(int i=1;i<=n;i++){
            int l=0,r=min(i-1,n-i);
            while(l<r){
                int mid=(l+r+1)>>1;
                if(query1(i-mid,i-1)==query2(i+1,i+mid))l=mid;
                else r=mid-1;
            }
            ans=max(ans,l<<1|1);
            l=0,r=min(i-1,n-i+1);
            while(l<r){
                int mid=(l+r+1)>>1;
                if(query1(i-mid,i-1)==query2(i,i+mid-1)) l=mid;
                else r=mid-1;
            }
            ans=max(ans,l<<1);
        }
        cout<<"Case "<<cnt<<": "<<ans<<'\n';
    }
}

J – Palindrome Reversion

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+10;
const int P=131;

char s[N];

int n;

unsigned long long h[N],p[N],f[N];

unsigned long long query1(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}

unsigned long long query2(int l,int r){
    return f[l]-f[r+1]*p[r-l+1];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>(s+1);
    n=strlen(s+1);
    p[0]=1;
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+s[i];
    }
    for(int i=n;i>=1;i--){
        f[i]=f[i+1]*P+s[i];
    }
    int l1=1,r1=n;
    while(s[l1]==s[r1]&&l1<r1) l1++,r1--;
    if(l1>r1) swap(l1,r1);
    int m=(r1-l1+1)/2;
    for(int i=0;i<=m;i++){
        if(query1(l1,l1+i-1)==query1(l1+i,l1+i+i-1)&&query1(l1+i+i,r1)==query2(l1+i+i,r1)){
            cout<<l1+i<<' '<<r1<<'\n';
            return 0;
        }
        else if(query1(l1,l1+i-1)==query1(r1-i+1,r1)&&query1(l1+i,r1-i)==query2(l1+i,r1-i)){
            cout<<r1-i+1<<' '<<r1<<'\n';
            return 0;
        }
        else if(query1(r1-i+1,r1)==query1(r1-i-i+1,r1-i)&&query1(l1,r1-i-i)==query2(l1,r1-i-i)){
            cout<<l1<<' '<<r1-i<<'\n';
            return 0;
        }
    }
    cout<<"-1 -1\n";
}