POJ - 3080 Blue Jeans 【KMP+暴力】(最大公共字串)

时间:2022-03-19 07:57:23

<题目链接>

题目大意:

就是求k个长度为60的字符串的最长连续公共子串,2<=k<=10

限制条件:

1、  最长公共串长度小于3输出   no significant commonalities

2、  若出现等长的最长的子串,则输出字典序最小的串

解题分析:

将第一个字串的所有子串枚举出来,然后用KMP快速判断该子串是否在所有主串中出现,如果都出现过,那么就按该子串的长度和字典序,不断更新答案,直到得到最终的最优解。

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=+;
const int M=+; string s[N];
int nxt[M]; void getnext(string str,int len){
int i=,j=-;
nxt[]=-;
while(i<len){
if(j==-||str[i]==str[j])
nxt[++i]=++j;
else j=nxt[j];
}
}
bool kmp(string s1,int len1,string s2,int len2){
int i=,j=;
while(i<len1){
if(j==-||s1[i]==s2[j])
++i,++j;
else j=nxt[j];
if(j==len2)return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int T,n;
cin>>T;
while(T--){
cin>>n;
for(int i=;i<n;i++)cin>>s[i];
string ans="";
for(int i=;i<s[].size();i++) //起点
{
for(int j=;i+j<=s[].size();j++) //长度
{
string res=s[].substr(i,j);
getnext(res,res.size());
bool flag=;
for(int k=;k<n;k++)
if(!kmp(s[k],s[k].size(),res,res.size()))
flag=;
if(!flag)
{
if(ans.size()<res.size())ans=res; //优先长度更长的公共子串
else if(ans.size()==res.size())ans=min(ans,res); //长度相同,按字典序排序
}
}
}
if(ans.size()<)cout<<"no significant commonalities"<<endl;
else cout<<ans<<endl;
}
return ;
}

2018-08-07