QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#851405 | #8701. Border | ANIG | 0 | 13ms | 56568kb | C++14 | 1.7kb | 2025-01-10 18:35:49 | 2025-01-10 18:35:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e6+5,mods=1e9+9;
string s,t;
int n,p1[N],p2[N],f1[N],f2[N],h[N],pw[N];
set<int>jl;
vector<int>g[N];
int rdc(ll x){
return (x%mods+mods)%mods;
}
int gets(int l,int r){
return rdc(h[r]-1ll*h[l-1]*pw[r-l+1]%mods);
}
int gets(int l,int r,int k,int b){
if(k<l||k>r)return gets(l,r);
return rdc(1ll*gets(l,k-1)*pw[r-k+1]%mods+1ll*b*pw[r-k]%mods+gets(k+1,r));
}
signed main(){
cin>>s>>t;
jl.insert(0);
n=s.size();
for(int i=1;i<=n;i++)p1[i]=s[i-1]-'a'+1,p2[i]=t[i-1]-'a'+1;
pw[0]=1;
for(int i=1;i<=n;i++)h[i]=(1ll*h[i-1]*131+p1[i])%mods,pw[i]=1ll*pw[i-1]*131%mods;
f1[1]=n;
while(p1[f1[2]+1]==p1[f1[2]+2])f1[2]++;
for(int i=3,k=2;i<=n;i++){
int to=i-k+1;
if(i+f1[to]<k+f1[k])f1[i]=f1[to];
else{
f1[i]=max(0,k+f1[k]-i);
while(p1[f1[i]+1]==p1[i+f1[i]])f1[i]++;
k=i;
}
}
reverse(p1+1,p1+n+1);
f2[1]=n;
while(p1[f2[2]+1]==p1[f2[2]+2])f2[2]++;
for(int i=3,k=2;i<=n;i++){
int to=i-k+1;
if(i+f2[to]<k+f2[k])f2[i]=f2[to];
else{
f2[i]=max(0,k+f2[k]-i);
while(p1[f2[i]+1]==p1[i+f2[i]])f2[i]++;
k=i;
}
}
reverse(p1+1,p1+n+1);
reverse(f2+1,f2+n+1);
for(int i=1;i<=n;i++){
if(f1[n-i+1]==i)jl.insert(i);
else{
if(2*i<=n){
if(f1[n-i+1]+f2[i]+1==i){
g[f1[n-i+1]+1].push_back(i);
g[n-f2[i]].push_back(i);
}
}else{
if(gets(f1[n-i+1]+2,i-f2[i]-1)==gets(n-i+f1[n-i+1]+2,n-f2[i]-1)){
g[n-i+f1[n-i+1]+1].push_back(i);
}
}
}
}
for(int i=1;i<=n;i++){
int res=0;
for(int c=1;c<=n;c++){
if(gets(1,c,i,p2[i])==gets(n-c+1,n,i,p2[i]))res=max(res,c);
}
cout<<res<<"\n";
}
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 13ms
memory: 56568kb
input:
cbaababaabacbaababaabacbaabacbaababaabacbaaba dabbababbabaabbafabbgbaabfebaabzababbayaabcac
output:
45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45
result:
wrong answer 1st numbers differ - expected: '0', found: '45'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%