求调
查看原帖
求调
668379
Poole_tea楼主2023/11/3 18:49
#include<bits/stdc++.h>
using namespace std;
#define int __int128
const int MAXN=2e6+10;
const int mod=1e9+7;
const int base=131;
string c;
int sum1[MAXN],sum2[MAXN];
int b[MAXN];
inline int read() {
    int x = 0, f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        f |= ch == '-', ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}
inline void write(int x)
{
    if(x<0){
        x=-x;
        putchar('-');
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void k(string x){
	for(int i=1;i<=x.size();i++){
		sum1[i]=(sum1[i-1]*base+x[i])%mod;
		b[i]=(b[i-1]*base)%mod;
	}
}
inline void kkk(string x){
	for(int i=x.size()-1;i>=1;i--){
		sum2[i]=(sum2[i+1]*base+x[i])%mod;
	}
}
inline int sb(int l,int r){
	return ((sum1[r]-sum1[l-1]*b[r-l+1])%mod)+mod%mod;
}
inline int hk(int l,int r){
	return ((sum2[r]-sum2[l+1]*b[l-r+1])%mod)+mod%mod;
}
signed main(){
	int n;
	n=read();
	cin>>c;
	c=" "+c;
	b[0]=1;
	k(c);
	kkk(c);
//	write(n);
//	write(hk(2*n,2+n+1));
    for(int i=0;i<=n;i++){
        if(sb(1,i)==hk(i+n,n+1)&&sb(i+1,n)==hk(2*n,i+n+1)){
        	for(int j=n+i;j>=i+1;j--){
        		cout<<c[j];
			}
			puts("");
			write(i);
			puts("");
			return 0;
		}
	}
	cout<<-1<<endl;
//    cout<<sum2[6]<<" "<<sum1[1];
}
2023/11/3 18:49
加载中...