出题人题解 | #tokitsukaze and Similar String#

原题解链接：https://ac.nowcoder.com/discuss/150249

$hashhash$练习题。

预处理所有$2626$种变化的$hashhash$表，用$hashhash$表来判断子串是否相等。

假设$xx$的第$ii$种变化与$yy$相等，$ans=min(i,26-i)ans=min(i,26-i)$。

都不相等就$-1-1$。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int maxn = 2e5+100;
/*
 * char* 1-bas
 * sum[i] = s[i]+s[i-1]*Seed+s[i-2]*Seed^2+...+s[1]*Seed^(i-1)
 */
ULL Seed_Pool[]={19260817,91815541};
ULL Mod_Pool[]={1000000009,4294967291ull};
ULL bas[maxn];

ULL Seed,Mod;
struct Hash_1D{
    ULL sum[maxn];
    void init(char *s ,int n,int seedIndex,int modIndex,char ch){
        static bool first_use = true;
        //cerr<<first_use<<endl;

        if (first_use){
            Seed = Seed_Pool[seedIndex];
            Mod = Mod_Pool[modIndex];
            bas[0]=1;
            for (int i=1;i<=n;i++){
                bas[i] = bas[i-1]*Seed%Mod;
            }
            first_use = false;
        }
        for (int i=1;i<=n;i++){
            // cerr<<s[i]<<" "<<ch<<endl;
            int delta =(s[i] == ch?1:0);
            sum[i] = (sum[i-1]*Seed%Mod+delta)%Mod;
        }
    }

    ULL getHash(int l,int r){
        return (sum[r]-sum[l-1]*bas[r-l+1]%Mod+Mod)%Mod;
    }
}hasher[26];
char s[maxn];
int used[26];
vector<ULL> get_vec(int l,int r){
    vector<ULL> res(0);
    for (int i=0;i<26;i++){
        res.push_back(hasher[i].getHash(l,r));
    }
    return res;
}
bool check(const vector<ULL> & v1,const vector<ULL>&v2,int delta){
    bool succ = true;
    for (int i=0;i<26;i++){
        if (v1[(i+delta)%26] != v2[i]){
            succ = false;
            break;
        }
    }
    if (succ)return true;
    succ = true;
    for (int i=0;i<26;i++){
        if (v2[(i+delta)%26] != v1[i]){
            succ = false;
            break;
        }
    }
    if (succ)return true;
    return false;
}
void solve(){
    int x,y,len;
    scanf("%d%d%d",&x,&y,&len);
    vector<ULL> vec1 = get_vec(x,x+len-1);
    vector<ULL> vec2 = get_vec(y,y+len-1);
    int ans =-1;
    for (int delta = 0;delta <26;delta++){
        if (check(vec1,vec2,delta)){
            printf("%d\n",delta);
            return;
        }
    }
    printf("%d\n",-1);
}
int main(){
    int n,m;
    scanf("%d",&n);
    scanf("%s",s+1);
    for (char ch = 'a';ch<='z';ch++){
        hasher[ch - 'a'].init(s,n,1,1,ch);
    }
    scanf("%d",&m);
    while (m--){
        solve();
    }

    return 0;
}