QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#179335#7238. Two StringsPhantomThreshold#AC ✓0ms7652kbC++201.5kb2023-09-14 20:39:352023-09-14 20:39:35

Judging History

This is a historical verdict posted at 2023-09-14 20:39:35.

  • [2023-09-14 20:57:16]
  • 管理员手动重测本题所有提交记录
  • Verdict: AC
  • Time: 208ms
  • Memory: 420268kb
  • [2023-09-14 20:39:35]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 7652kb
  • [2023-09-14 20:39:35]
  • Submitted

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'