时间限制: 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

数据范围及提示 Data Size & Hint

直接上代码

#include <iostream> #include <algorithm> #include <cstring>//找一堆字符串中的最长公共子串（题目没有规定出现相同长度的最长公共子串如何解决，也没有保证测试数据不会出现有相同长度的最长公共子串的情况） using namespace std; int n,m=1;string s[100];string fun(string a, string b){ string c,temp; if(a.length()<=b.length()) { for(int i=0;i<a.length();i++) { int k=i; for(int j=0;j<b.length();j++) { int l=j; while(a[k]==b[l]&&k<a.length()&&l<b.length()) { temp+=a[k]; k++; l++; } if(temp.length()>=c.length()) { c=temp; } temp.clear(); k=i; } } } else { string d=a; a=b; b=d; for(int i=0;i<a.length();i++) { int k=i; for(int j=0;j<b.length();j++) { int l=j; while(a[k]==b[l]&&k<a.length()&&l<b.length()) { temp+=a[k]; k++; l++; } if(temp.length()>=c.length()) { c=temp; } temp.clear(); k=i; } }  } if(m==n-1) return c; else return fun(c,s[++m]);}int main(){  cin>>n; for(int i=0;i<n;i++) { cin>>s[i]; } cout<<fun(s[0],s[1])<<endl;} 

超级暴力解法

#include<bits/stdc++.h>using namespace std;string a[22];bool cmp(string a,string b){return a.length()<b.length();}int main(){ int n,ans,len,i; cin>>n; for(int i=1;i<=n;i++)  {cin>>a[i]; } sort(a+1,a+n+1,cmp); len=a[1].length(); for(ans=len;ans>=1;ans--) {bool wang=false,y=false; for(i=0;i<=len-ans;i++) { int jishu=1; for(int j=2;j<=n;j++)//一个个匹配  { int lenx=a[j].length(); for(int q=0;q<=lenx-ans;q++) { y=true;  for(int k=q;k<=ans+q-1;k++) { if(a[j][k]!=a[1][i+k-q]) { y=false;break; } } if(y==true)  {jishu++;break; } else y=true; }  } if(jishu==n)  {wang=true;break; } } if(wang){break; } } for(int s=i;s<=i+ans-1;s++) cout<<a[1][s];}