1 条题解
-
0
#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e6+10,B=131,P=998244353; char st[N]; int s1[N],s2[N]; int qpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;} int get(int l,int r){if(l>r)return 0;return ((s1[r]-s1[l-1]*qpow(B,r-l+1))%P+P)%P;} int get1(int l,int r){if(l>r)return 0;return ((s2[l]-s2[r+1]*qpow(B,r-l+1))%P+P)%P;} signed main() { int n;cin>>n; scanf("%s",st+1); for(int i=1;i<=n*2;i++)s1[i]=(s1[i-1]*B+st[i])%P; for(int i=n*2;i>=1;i--)s2[i]=(s2[i+1]*B+st[i])%P; for(int i=0;i<=n;i++) { int sum1=get1(i+1,i+n),sum2=(get(1,i)*qpow(B,n-i)+get(i+n+1,n*2))%P; if(sum1==sum2) { for(int j=1;j<=i;j++)cout<<st[j]; for(int j=i+n+1;j<=n*2;j++)cout<<st[j]; cout<<'\n'<<i<<'\n'; return 0; } } cout<<-1; return 0; }
- 1
信息
- ID
- 7804
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 2
- 上传者