2023-01-09

题目算法

Z函数,KMP,字符串Hash

解题思路

对于一个 \(f_S\)，我们可以将它化成三个部分。
也就是 \([0,i-1],[i,i+n-1],[i+n,2n]\)。
我们可以不断枚举中断点 ii，判断中间子串是否是原字符串的回文串，时间复杂度 \(O(n^2)\)。
我们不得不寻找一种更好的方法，对此我们可以把它切成四部分。
即 \([0,i-1],[i,n],[n+1,i+n-1],[i+n,2n]\)。
仅当 \(T\) 是合法的字符串，有 \(i\) 满足 \([0,i-1]\) 和 \([n+1,i+n-1],[i,n]\) 和 \([i+n,2n]\) 互为回文数。
为了运算方便，我们可以把 \([n+1,2n]\) 翻转过来。
显然的，\([0,n]\) 绝对是 \([n+1,2n]\) 右移复制后的子串。
我们只要找到 \([0,n]\) 在 \([n+1,2n][n+1,2n]\) 串中的位置，逆推之后，我们就能确定 \(i\) 的位置，这道题就做完了。

完成状态

已完成

Code

#include<bits/stdc++.h>
using namespace std;
char s[2000005],a[2000005],b[2000005];
int n,x;
int main(){
	cin>>n>>s;
	for(int i=0;i<n;i++){
		a[i]=s[i];
		b[i]=b[n+i]=s[n*2-i-1];
	}
	auto x=strstr(b,a);
	if(!x)puts("-1");
	else{
		int i=n-(x-b);
		for(int j=0;j<i;j++)printf("%c",s[j]);
		for(int j=n+i;j<2*n;j++)printf("%c",s[j]);
		cout<<endl;
		cout<<i;
	}
    return 0;
}