自动搬运

查看原文

来自洛谷，原作者为

	ChongYun INFP-T 5.21||坐标 HN-CS||真的想每场比赛都不挂分。

搬运于2025-08-24 23:03:15，当前版本为作者最后更新于2025-01-14 10:33:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

「同类串」的定义为对于两个等长的字符串 $s$ 和 $t$，所有位置上的字符都互相对应。目标是找出一个尽可能大的 $k$ 使得 $s, t$ 分别含有一个长度为 $k$ 的子串 $s', t'$，且 $s',t'$ 是「同类串」。

直接进行字符串哈希很难做。注意到答案 $k$ 具有单调性，我们可以进行二分答案将该问题转化为判断性问题。

从「同类串」的定义出发，所有字符出现位置相互对应和所有位置上的字符互相对应显然是等价的。

那我们不妨从字符出现的位置入手。

进一步地，两个为一组「同类串」的字符串里的所有字符上一次出现的位置一定相同。

故存下每一个位置上一个出现该位置上的字符的位置，判断两个字符串中是否存在长度固定的区间里所有字符上一次出现的位置相同。

使用哈希维护一个滑动窗口，每次滑动单位长度 $1$ 的长度。设当前的固定长度为 $k$，滑动到的左端点为 $i$。可以提前预处理出字符上一次出现的位置、下一次出现该字符的位置，以做到 $\mathcal{O}(1)$ 地从上一个 $[i-1,i+k-2]$ 的窗口滑动到 $[i,i+k-1]$ 的窗口。

故判断函数可以 $\mathcal{O}(n)$ 解决。总时间复杂度为 $\mathcal{O}(n\log^2 n)$。

Code

/* 云云珂爱 */
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
int n,m;
string S,T;
ull base=1e5+3,qpow[100005];
ull lstS[205],lstT[205];
ull nowS[100005],nowT[100005];
ull nxtS[100005],nxtT[100005];
ull HashS[100005],HashT[100005];
map<ull,int> vis;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
bool check(int x){
	vis.clear();
	memset(lstS,0,sizeof(lstS));
	memset(lstT,0,sizeof(lstT));
	for(int i=1;i<=n;i++) nxtS[i]=-1;
	for(int i=1;i<=m;i++) nxtT[i]=-1;
	for(int i=1;i<=n;i++) nowS[i]=max(n,m)+1;
	for(int i=1;i<=m;i++) nowT[i]=max(n,m)+1;
	for(int i=1;i<=n;i++){
		if(lstS[S[i]]) nxtS[lstS[S[i]]]=i,nowS[i]=i-lstS[S[i]];
		lstS[S[i]]=i;  
	}
	for(int i=1;i<=m;i++){
		if(lstT[T[i]]) nxtT[lstT[T[i]]]=i,nowT[i]=i-lstT[T[i]];
		lstT[T[i]]=i; 
	}
	ull now=0;
	for(int i=1;i<=x;i++) now=now*base+nowS[i];
	vis[now]=1;
	for(int i=2;i+x-1<=n;i++){
		now-=nowS[i-1]*qpow[x-1];
		now=now*base+nowS[i+x-1];
		if(nxtS[i-1]){
			int qwq=i+x-1-nxtS[i-1];
			if(nxtS[i-1]<=i+x-1){
				now-=nowS[nxtS[i-1]]*qpow[qwq];
				nowS[nxtS[i-1]]=max(n,m)+1;
				now+=nowS[nxtS[i-1]]*qpow[qwq];
			}
			else if(nxtS[i-1]<=n) nowS[nxtS[i-1]]=max(n,m)+1;
		}
		vis[now]=1;
	}
	now=0;
	for(int i=1;i<=x;i++) now=now*base+nowT[i];
	if(vis[now]) return 1;
	for(int i=2;i+x-1<=m;i++){
		now-=nowT[i-1]*qpow[x-1];
		now=now*base+nowT[i+x-1];
		if(nxtT[i-1]){
			int qwq=i+x-1-nxtT[i-1];
			if(nxtT[i-1]<=i+x-1){
				now-=nowT[nxtT[i-1]]*qpow[qwq];
				nowT[nxtT[i-1]]=max(n,m)+1;
				now+=nowT[nxtT[i-1]]*qpow[qwq];
			}
			else if(nxtT[i-1]<=m) nowT[nxtT[i-1]]=max(n,m)+1;
		}
		if(vis[now]) return 1;
	}
	return 0;
}
signed main(){
	cin>>S>>T;
	n=S.size(); m=T.size();
	S=" "+S; T=" "+T;
	qpow[0]=1;
	for(int i=1;i<=n;i++) qpow[i]=qpow[i-1]*base;
	int l=1,r=min(n,m),mid,ans;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)){
			l=mid+1;
			ans=mid;
		} 
		else r=mid-1;
	} 
	printf("%lld\n",ans);
	return 0;
}

2025.2.8 upd：忘记map的 $\log$ 了，总时间复杂度更正为 $O(n\log^2n)$。