自动搬运

查看原文

来自洛谷，原作者为

	General0826 本人一刚学一年 九个月的蒟蒻，非常的菜.| 如果遇到困难就gengen呼救 | liyifan202201 是我爹

搬运于2025-08-24 22:11:52，当前版本为作者最后更新于2024-10-23 14:50:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解 P5546 【[POI2000]公共串】

我在知道这个题之前出了一道这 Gen_UNO ，我还是只井底之蛙罢了。

KMP 做法

我们考虑暴力的做法，因为公共串肯定是一个串的子串 （和废话一样），去截取一个串的子串。对与每个串跑 KMP。时间 $O(nm^3)$，非常爆炸（$m$ 是字符长度）。

你考虑一件这样的事：

我们直接跑 KMP 看匹不匹配，是一个 bool，要这样搞 hash 也能替代。KMP 有一个中途前缀匹配度，前缀匹配度？哦！那我们将本来的子串换成一个串的后缀。因为单调性，$[l,r]$ 可以，肯定 $[l,r-1]$ 可以。这样就一次将所有 $l$ 相等的就统计了，将这个前缀匹配度取 $\max$。

但这只是一个串是，因为是公共的对于每个串，这个再对这取 $\min$ 。因为这个值只是一个后缀的贡献。所以又要将这个值再取 $\max$，时间 $O(nm^2)$，很蓟县。

这过程就如 Gen_UNO 中的所说：

他至少需要多少张牌才可以被任何人决斗的情况中得到最少的冰红茶最多

以下是代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,ans=0;
string a[N],cp;
int nxt[N];
void inti(string s){
	nxt[0]=-1;
	for(int i=0,j=-1;i<s.size();){
		if(s[i]==s[j]||j==-1)
			nxt[++i]=++j;
		else
			j=nxt[j];
	}
}
int KMP(string a,string b){
	int ans=-1;
	for(int i=0,j=0;i<a.size();){
		if(a[i]==b[j]&&j==b.size()-1){
			return b.size();
		}
		else if(a[i]==b[j]||j==-1){
			ans=max(ans,j);
			i++;j++;
		}
		else
			j=nxt[j];
	}
	return ans+1;
}
int cheke(string b){
	int ans=1e9;
	inti(b);
	for(int i=1;i<=n;i++)
		ans=min(KMP(a[i],b),ans);
	return ans;
}
int main() {
  	cin>>n;
  	for(int i=1;i<=n;i++){
  		cin>>a[i]; 
	}
	for(int i=0;i<a[1].size();i++){
		string cp="";
		for(int j=i;j<a[1].size();j++)
			cp+=a[1][j];
		ans=max(cheke(cp),ans);
	}
	cout<<ans;
  	return 0;
}