Codevs 1425 最长公共子串

1425 最长公共子串

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 青铜 Bronze
 
 
 
题目描述 Description

输入N(2<=N<=20)个字符串,输出最长公共子串。

输入描述 Input Description

输入N

再输入N个字符串

输出描述 Output Description

输出最大公共子串。

样例输入 Sample Input

3

abce

cabk

jaab

样例输出 Sample Output

ab

/*
好像这种求多串最长公共子串要用后缀数组或者自动机什么的
我这个就比较暴力了
*/
#include<iostream>
#include<string>
using namespace std;
const int N=;
int INF=<<;
int a[N],n1;
string str[N];
int main(){
cin>>n1;
for(int i=;i<n1;i++){
cin>>str[i];
if(INF>str[i].size())
INF=str[i].size();
}
if(n1==){
cout<<str[];
return ;
}
for(int i=INF;i;i--){//枚举长度为INF的子串,从大往小
for(int j=;j<str[].size()-i;j++){//从第一个位置开始枚举子串
bool flag=true;
for(int k=;k<n1;k++)
if(str[k].find(str[].substr(j,i) )== string::npos)
flag=false;
if(flag){
cout<<str[].substr(j,i);
return ;
}
}
}
return ;
}
上一篇:【wikioi】3160 最长公共子串(后缀自动机)


下一篇:【SAM】codevs3160-最长公共子串