C++(g++ 7.5.0) 解法, 执行用时: 190ms, 内存消耗: 100068K, 提交时间: 2023-04-18 22:33:24

#include<bits/stdc++.h>

using namespace std;
const int N = 5e5 + 10, M = N << 1;
char s[N], q[N];
int ch[M][26], len[M], fa[M], tot = 1, np = 1, ans[M];

void extend(int c)
{
	int p = np; np = ++tot;
	len[np] = len[p] + 1;
	while (p && !ch[p][c]) {
		ch[p][c] = np;
		p = fa[p];
	}
	if (!p) {
		fa[np] = 1;
	}
	else {
		int q = ch[p][c];
		if (len[q] == len[p] + 1) {
			fa[np] = q;
		}
		else {
			int nq = ++tot;
			len[nq] = len[p] + 1;
			fa[nq] = fa[q], fa[q] = fa[np] = nq;
			while (p && ch[p][c] == q) {
				ch[p][c] = nq;
				p = fa[p];
			}
			memcpy(ch[nq], ch[q], sizeof ch[q]);
		}
	}
}

signed main()
{
	scanf("%s", s);
	for (auto ch : s) {
		extend(ch - 'a');
	}
	scanf("%s", q);
	int t = 0, p = 1;
	for (int i = 0; q[i]; ++i) {
		int c = q[i] - 'a';
		while (p > 1 && !ch[p][c]) {
			p = fa[p];
			t = len[p];
		}
		if (ch[p][c]) ++t, p = ch[p][c];
		ans[p] = max(ans[p], t);
	}
	int res = -1;
	for (int i = 1; i <= tot; ++i) {
		res = max(res, ans[i]);
	}
	printf("%d\n", res);

	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 2153ms, 内存消耗: 21940K, 提交时间: 2023-01-07 11:26:37

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
typedef long long LL;
int rk[2*N],sa[2*N],oldrk[2*N],ht[2*N];
int main()
{
	string s,t,str;
	cin>>str>>t;
	s=str+"#"+t;
	int n=s.length();
	s="?"+s;
	for(int i=1;i<=n;i++)sa[i]=i,rk[i]=s[i];
	for(int w=1;w<n;w<<=1)
	{
		sort(sa+1,sa+n+1,[&](int x,int y){
			return rk[x]==rk[y]?rk[x+w]<rk[y+w]:rk[x]<rk[y];
		});
		memcpy(oldrk,rk,sizeof rk);
		for(int i=1,p=0;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,h=0;i<=n;i++)
	{
		if(rk[i]==0)continue;
		int j=sa[rk[i]-1];
		if(h)h--;
		while(s[i+h]==s[j+h])h++;
		ht[rk[i]]=h;
	}
	int res=0;
	for(int i=2;i<=n;i++)
	{
		if(sa[i]<=str.length()&&sa[i-1]>str.length()+1||(sa[i]>str.length()+1&&sa[i-1]<=str.length()))
		res=max(res,ht[i]);
	}
	cout<<res;
}