QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179335 | #7238. Two Strings | PhantomThreshold# | AC ✓ | 0ms | 7652kb | C++20 | 1.5kb | 2023-09-14 20:39:35 | 2023-09-14 20:39:35 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const int maxn = 2050000;
struct SAM
{
int las,rt,tot;
int par[maxn],len[maxn];
int son[maxn][26];
int newnode(int L)
{
++tot;
memset(son[tot],0,sizeof son[tot]);
par[tot]=0;
len[tot]=L;
return tot;
}
void init()
{
tot=0;
las=rt=newnode(0);
}
void extend(const int w)
{
int p=las;
int np=newnode(len[p]+1);
while(p && !son[p][w]) son[p][w]=np,p=par[p];
if(!p) par[np]=rt;
else
{
int q=son[p][w];
if(len[q]==len[p]+1) par[np]=q;
else
{
int nq=newnode(len[p]+1);
memcpy(son[nq],son[q],sizeof son[nq]);
par[nq]=par[q];
par[np]=par[q]=nq;
while(p&&son[p][w]==q) son[p][w]=nq,p=par[p];
}
}
las=np;
}
}tr;
string S,T;
int sn,tn;
int ansx,ansy,ans=INT_MIN;
signed main()
{
ios_base::sync_with_stdio(false); ////////////////////////////////////////
cin.tie(0);
cin>>S; sn=S.size(); S=' '+S;
cin>>T; tn=T.size(); T=' '+T;
tr.init();
for(int i=1;i<=tn;i++) tr.extend(T[i]-'a');
ansx=0,ansy=0;
int p=tr.rt, L=0;
for(int i=1;i<=sn;i++)
{
const int w=S[i]-'a';
while(p!=tr.rt && !tr.son[p][w]) p=tr.par[p],L=tr.len[p];
if(tr.son[p][w])
{
p=tr.son[p][w];
L++;
}
if(L)
{
int temp= L-max(i-L+1-1,sn-i);
if(temp>ans)
{
ans=temp;
ansy=i;
ansx=i-L+1;
}
}
}
cout<<ansx-1<<' '<<ansy-1<<endl;
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 7652kb
input:
2 2 1
output:
0 0
result:
wrong answer 1st numbers differ - expected: '2', found: '0'