一个字符串S从第i个字符开始分开两半,左边为A,右边为B,整个字符串的逆序为C。现在知道ACB,求原来的字符串是什么,如果无解输出-1。
#include <stdio.h>
const int N=2000050, E=37173, mo=1e9+7;
int n, m, i, j, k;
long long x, y, a[N], e[N], A[N];
char s[N];
int haxi(int l, int r){
return a[r]-a[l-1]*e[r-l+1]%mo;
}
int main(){
scanf("%d%s", &n, s+1);
m = n * 2;
for(e[0]=i=1; i<=m; i++){
a[i] = (a[i-1]*E + s[i]) % mo;
e[i] = e[i-1] * E % mo;
}//顺序哈希值
for(i=m; i>=1; i--){
A[i] = (A[i+1]*E + s[i]) % mo;
}//倒序哈希值
for(i=0; i<=n; i++){
x = a[i]*e[n-i] + haxi(i+n+1, m);//拼接哈希值
y = A[i+1] - A[i+n+1]*e[n];//倒序哈希值
if((x%mo+mo)%mo == (y%mo+mo)%mo) break;
}//前i个 + 倒序列 + 后面的
if(i > n) printf("-1\n");
else{
for(k=i+n; k>=i+1; k--) printf("%c", s[k]);
printf("\n%d\n", i);//输出答案
}
return 0;
}