博主链接
题目链接
题意:
给你n个字符串,问你这n个串的最长公共子串
题解:
题目和HDU-1238感觉差不多,暴力枚举任意一个字符串的所有子串,然后暴力匹配,这里用string解决的;
代码:
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4050;
const int mod=1e9+7;
string s[maxn];
int main(){
int n;
ios::sync_with_stdio(0);
while((cin>>n)&&n!=0){
for(int i=1;i<=n;i++){
cin>>s[i];
}
string t;
int cot=0;
int maxx=0;
int len=s[1].size();
for(int i=0;i<len;i++){
for(int j=1;j<=len-i;j++){ //枚举子串长度
if(j<maxx)continue;
cot=0;
for(int k=2;k<=n;k++){
if(s[k].find(s[1].substr(i,j))==string::npos)break; //string函数查找
else cot++;
}
if(cot==n-1){ //如果这个子串出现了n-1次,选取的那个串本身就有一次,则维护maxx
if(maxx<j){
maxx=j;
t=s[1].substr(i,j);
}
else if(maxx==j){
if(t>s[1].substr(i,j))t=s[1].substr(i,j);
}
}
}
}
if(maxx==0)cout<<"IDENTITY LOST"<<endl;
else cout<<t<<endl;
}
return 0;
}