这题用扩展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(""); } }