Clairewd’s message HDU - 4300

这题用扩展kmp或者hash都可以做
我是用的hash
但是或者扩展kmp更方便一点？
这种题，字符串颠来倒去的比较绕。但是其实是不难的

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ull,ull> pull;
const int max_n = 1e5+100;
struct My_Hash{
    ull base = 131;
    ull mm0=1e9+7,mm1=1e9+9;
    ull p0[max_n],p1[max_n];
    ull ha0[max_n],ha1[max_n];
    void Insert(char s[]){
        int n = strlen(s+1);
        p0[0]=p1[0]=1;
        ha0[0]=ha1[0]=0;
        for (int i=1;i<=n;++i){
            p0[i]=p0[i-1]*base%mm0;
            p1[i]=p1[i-1]*base%mm1;
            ha0[i]=(ha0[i-1]*base%mm0+s[i])%mm0;
            ha1[i]=(ha1[i-1]*base%mm1+s[i])%mm1;
        }
    }
    pull gethash(int l, int r){
        ull ans0 = (ha0[r]-ha0[l-1]*p0[r-l+1]%mm0+mm0)%mm0;
        ull ans1 = (ha1[r]-ha1[l-1]*p1[r-l+1]%mm1+mm1)%mm1;
        return pull(ans0,ans1);
    }
}S0,S1;
char table[30];
char text[max_n];
char txt[max_n];
int n;
char revtable[30];

int main(){
    int T;scanf("%d",&T);
    while (T--){
        scanf("%s",table);
        for (int i=0;i<26;++i)revtable[table[i]-'a']=(char)('a'+i);
        scanf("%s",text+1);
        n=strlen(text+1);
        for (int i=1;i<=n;++i)txt[i]=table[text[i]-'a'];
        txt[n+1]='\0';
        S0.Insert(text);S1.Insert(txt);
        int l=1,r=n;
        for (int i=(n+1)/2+1;i<=n;++i){
            if (S1.gethash(i,n)==S0.gethash(1,n-i+1)){
                l = n-i+2;r = i-1;
                break;
            }
        }
        printf("%s",text+1);
        for (int i=l;i<=r;++i)printf("%c",revtable[text[i]-'a']);
        puts("");
    }
}