题目描述
给你n个字符串，问其最长的公共串是啥。如果长度都是最长，输出字典序小的。
Sample Input3
aabbaabb
abbababb
bbbbbabb2xyzabc0
Sample OutputabbIDENTITY LOST
解题思路
取第一个字符串O(n^2)遍历，对其他字符串直接strstr匹配即可。 用KMP当然最好。
用ans存放当前的最优解。
下面是代码
#include <cstdio>#include <cstring>const int maxn = 210;int n;int anslen = 0;char ans[maxn];char s[4010][maxn];char p[maxn];//模式串int main(){while(scanf("%d",&n) && n) {anslen = 0;for(int i = 0 ; i < n ; i ++) scanf("%s",s[i]);/** 遍历s[0] */int len1 = strlen(s[0]);for(int i = 0 ; i < len1 ; i ++) {for(int j = i ; j < len1 ; j ++) {/** 模式串是s[0][i,i+1,…,j] */for(int k = i ; k <= j ; k ++) {p[k-i] = s[0][k];}p[j-i+1] = '\0';/** 模式串已就绪 */bool flag = true;//记录其他主串是否都有p串int len = j-i+1;//长度if(len < anslen) continue;for(int k = 1 ; k < n ; k ++) {if(strstr(s[k],p) == NULL) {flag = false;break;}}if(flag) {if(len == anslen) {//看字典序if(strcmp(p,ans) < 0) {strcpy(ans,p);}}else {strcpy(ans,p);anslen = len;}}}}if(anslen > 0) printf("%s\n",ans);else printf("IDENTITY LOST\n");}return 0;}
，捕捉最后的流星，坐在最高的山顶上，可以听音乐，聊电影，
