SA解法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,p,sa[2000010],rk[2000010],oldrk[2000010],id[2000010],cnt[2000010],st[2000010][25],lg2[2000010];
int get(int l,int r){
	r--;
	int d=lg2[r-l+1];
	return min(st[l][d],st[r-(1<<d)+1][d]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s,t;
	cin>>s>>t;
	int ST=s.size()+2;
	s=" "+s+'#'+t;
	n=s.size()-1;
	for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	m='z';
	for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i;i--)sa[cnt[rk[i]]--]=i;
	for(int w=1;p<n;w<<=1,m=p){
		int cur=0;
		for(int i=n-w+1;i<=n;i++)id[++cur]=i;
		for(int i=1;i<=n;i++)if(sa[i]>w)id[++cur]=sa[i]-w;
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++)cnt[rk[i]]++;
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i;i--)sa[cnt[rk[id[i]]]--]=id[i];
		p=0;
		memcpy(oldrk,rk,sizeof(rk));
		for(int i=1;i<=n;i++){
			if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		}
	}
	for(int i=1,k=0;i<=n;i++){
		if(rk[i]==n)continue;
		if(k)k--;
		while(s[i+k]==s[sa[rk[i]+1]+k])k++;
		st[rk[i]][0]=k;
	}
	for(int i=1;i<=22;i++){
		for(int x=1;x+(1<<i)-1<n;x++){
			st[x][i]=min(st[x][i-1],st[x+(1<<i-1)][i-1]);
		}
	}
	set<int> ss;
	for(int i=1;i<ST-1;i++)ss.insert(rk[i]);
	int l1=0,r1=0,l2=0,r2=0;
	int mx=0,l=0;
	for(int i=ST;i<=n;i++){
		auto it=ss.upper_bound(rk[i]);
		if(it!=ss.end()){
			int r=*it;
			int d=get(rk[i],r);
//			cout<<rk[i]<<" "<<r<<" "<<i<<" "<<sa[r]<<" "<<d<<'\n';
			if(d>mx){
				mx=d;
				l1=sa[r]-1;r1=sa[r]+d-1;
				l2=i-ST;r2=l2+d;
			}
		}
		if(it!=ss.begin()){
			int l=*(--it);
			int d=get(l,rk[i]);
			if(d>mx){
				mx=d;
				l1=sa[l]-1;r1=sa[l]+d-1;
				l2=i-ST;r2=l2+d;
			}
			
		}
	}
	cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<'\n';
	return 0;
}

SAM解法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ch[1000010][27],len[1000010],fa[1000010],id=1,np=1,ed[1000010];
void extend(int c,int x){
	int p=np;np=++id;
	len[np]=len[p]+1;
	ed[np]=x;
	for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
	if(!p)fa[np]=1;
	else{
		int q=ch[p][c];
		if(len[q]==len[p]+1)fa[np]=q;
		else{
			int nq=++id;
			len[nq]=len[p]+1;
			ed[nq]=ed[q];
			fa[nq]=fa[q];fa[q]=nq;fa[np]=nq;
			for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s,t;
	cin>>s>>t;
	for(int i=0;i<s.size();i++)extend(s[i]-'a',i);
	int p=1,l1=0,r1=-1,l2=0,r2=-1;
	int mx=0,l=0;
	for(int i=0;i<t.size();i++){
		int j=t[i]-'a';
		while(p&&!ch[p][j])p=fa[p],l=len[p];
		if(p){
			p=ch[p][j];
			l++;
			if(l>mx){
				mx=l;
				r1=ed[p];l1=r1-l+1;
				r2=i;l2=r2-l+1;
			}
		}
		else{
			p=1;
			l=0;
		}
	} 
	cout<<l1<<" "<<r1+1<<" "<<l2<<" "<<r2+1<<'\n';
	return 0;
}