题意分析

1. 问题核心：
   • 从两个长字符串中找出最长的公共子串，该子串即为可能的原始短信内容。
2. 输入特性：
   • 两个字符串包含相同的原始短信，但两侧可能添加了不同的冗余字符。
3. 输出要求：
   • 返回最长公共子串的长度。

解题思路

1. 后缀数组构建：
   • 将两个字符串拼接，中间用特殊字符分隔，构建后缀数组。
2. 高度数组计算：
   • 通过高度数组（$LCP$数组）寻找分属两个字符串的后缀的最长公共前缀。
3. 结果提取：
   • 遍历高度数组，记录满足条件的最大长度。

实现步骤

1. 字符串拼接：
   • 将两个输入字符串用未出现的字符（如$）连接，形成新字符串。
2. 后缀数组生成：
   • 使用倍增算法或$DC3$算法构建后缀数组。
3. $LCP$数组计算：
   • 通过$Kasai$算法计算高度数组。
4. 最长子串搜索：
   • 遍历高度数组，当相邻后缀属于不同原始字符串时，更新最大长度。
5. 输出结果：
   • 返回找到的最大长度值。

代码实现

#include<cstdio>
#include<cstring>
#define N 100000
#define Gmax(x,y) (x<(y)&&(x=(y)))
using namespace std;
int n,m;char s[(N<<1)+5];
class Class_SuffixArray//后缀数组
{
	private:
		int n,rk[(N<<1)+5],pos[(N<<1)+5],tot[(N<<1)+5];
		inline void RadixSort(int S)
		{
			register int i;
			for(i=0;i<=S;++i) tot[i]=0;
			for(i=1;i<=n;++i) ++tot[rk[i]];
			for(i=1;i<=S;++i) tot[i]+=tot[i-1];
			for(i=n;i;--i) SA[tot[rk[pos[i]]]--]=pos[i];
		}
		inline void GetSA(char *s)
		{
			register int i,k,cnt=0,Size=122;
			for(n=strlen(s),i=1;i<=n;++i) rk[pos[i]=i]=s[i-1];
			for(RadixSort(Size),k=1;cnt<n;k<<=1)
			{
				for(Size=cnt,cnt=0,i=1;i<=k;++i) pos[++cnt]=n-k+i;
				for(i=1;i<=n;++i) SA[i]>k&&(pos[++cnt]=SA[i]-k);
				for(RadixSort(Size),i=1;i<=n;++i) pos[i]=rk[i];
				for(rk[SA[1]]=cnt=1,i=2;i<=n;++i) rk[SA[i]]=(pos[SA[i-1]]^pos[SA[i]]||pos[SA[i-1]+k]^pos[SA[i]+k])?++cnt:cnt;
			}
		}
		inline void GetHeight(char *s)
		{
			register int i,j,k=0;
			for(i=1;i<=n;++i) rk[SA[i]]=i;
			for(i=1;i<=n;++i)
			{
				if(!(rk[i]^1)) continue;
				k&&--k,j=SA[rk[i]-1];
				while(i+k<=n&&j+k<=n&&!(s[i+k-1]^s[j+k-1])) ++k;
				Height[rk[i]]=k;
			}
		}
	public:
		int SA[(N<<1)+5],Height[(N<<1)+5];
		inline void Init(char *s) {GetSA(s),GetHeight(s);}
}S;
int main()
{
	register int i,ans=0;
	scanf("%s",s),n=strlen(s),s[n]='%',scanf("%s",s+n+1),m=strlen(s+n+1);
	for(S.Init(s),i=1;i<=n+m;++i) if((S.SA[i]<n)^(S.SA[i-1]<n)) Gmax(ans,S.Height[i]);//如果相邻两个后缀的起始字符不在同一个字符串内，就更新答案
	return printf("%d",ans),0;
}