题面
分析
注意读题
然后显然字符串哈希
(Code)
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
const LL P = 1e9 + 9 , B = 26;
LL b[N] , s1[N] , s2[N];
char st[30] , pt[30] , s[N];
int main()
{
scanf("%s%s" , st , s);
for(register int i = 0; i < 26; i++) pt[st[i] - 'a'] = i + 'a';
int len = strlen(s);
b[0] = 1;
for(register int i = 1; i <= len; i++) b[i] = b[i - 1] * B % P;
for(register int i = 0; i < len; i++) s1[i + 1] = (s1[i] * B % P + st[s[i] - 'a'] - 'a') % P;
for(register int i = 0; i < len; i++)
{
s2[i + 1] = (s2[i] * B % P + s[i] - 'a') % P;
if (i + i + 2 >= len && s2[len - i - 1] == ((s1[len] - s1[i + 1] * b[len - i - 1] % P) % P + P) % P)
{
printf("%s" , s);
for(register int j = len - i - 1; j <= i; j++) printf("%c" , pt[s[j] - 'a']);
break;
}
}
}