学习：
才开始自己，思路搞错了，先把前两个求最长公共子序列，然后依次用最长公共子序列与2,3,4，。。。m比较求最长公共子序列。。贡献了3次wa
直到看到这组数句才发现自己的错误：
13AAATTTGGGTTTGGGAAAGGGTTTAAAprint:AAA
按我的思路会输出TTT的。。唉。。因为前两个最长公共子序列为TTTGGG再将它与第三组比较时，就出来TTT了。而第1，2组可以得到AAA然后在于第三组的AAA才是正确结果。。。没有考虑全面。。
下面直接用函数strstr确定子序列位置爱查找，就避免了这样的错误。。
View Code #include#include #include #define maxn 65 using namespace std; char str[12][maxn]; char tmp[maxn],ans[maxn]; int n,m; void solve() { int i,j,k,l; int maxlen = 0; int len = strlen(str[0]); //O(60^2*m)复杂度 for (i = 0; i < len; ++i) { for (j = i; j < len; ++j) { memset(tmp,0,sizeof(tmp)); l = 0; for (k = i; k <= j; ++k) tmp[l++] = str[0][k];//找出子序列 for (k = 1; k < m; ++k) { if (strstr(str[k],tmp) == NULL)//判断子序列在串中出现的首位置，如果没有返回空 //第一次使用这个函数。。 break; } if (k == m) { if (l > maxlen) { strcpy(ans,tmp); maxlen = l; } else if (l == maxlen && strcmp(ans,tmp) > 0) { strcpy(ans,tmp); } } } } if (maxlen >= 3) printf("%s\n",ans); else printf("no significant commonalities\n"); } int main() { int i; cin>>n; while (n--) { cin>>m; for (i = 0; i < m; ++i) cin>>str[i]; solve(); } return 0; }
KMP算法实现
View Code #include#include #include #define maxn 65using namespace std;char str[12][maxn];char ans[maxn],tmp[maxn];int n,m;int next[maxn];void get_next(char *p,int len){ int i,j; i = 0; j = -1; next[0] = -1; while (i < len) { if (j == -1 || p[j] == p[i]) { i++; j++; next[i] = j; } else j = next[j]; }}bool kmp(char *p,int len){ int i,j,k; memset(next,0,sizeof(next)); get_next(p,len); for (k = 1; k < m; ++k) { int slen = strlen(str[k]); i = 0; j = 0; while (i < slen && j < len) { if (j == -1 || p[j] == str[k][i]) { i++; j++; } else { j = next[j]; } } if (j < len) break; } if (k == m) return true; else return false;}void solve(){ int i,j,k; int len = strlen(str[0]); int maxlen = 0; for (i = 0; i < len; ++i) { for (j = i; j < len; ++j) { memset(tmp,0,sizeof(tmp)); int l = 0; for (k = i; k <= j; ++k) { tmp[l++] = str[0][k]; } if (kmp(tmp,l)) { if (l > maxlen) { maxlen = l; strcpy(ans,tmp); } else if (l == maxlen) { strcpy(ans,tmp); } } } } if (maxlen >= 3) printf("%s\n",ans); else printf("no significant commonalities\n");}int main(){ int i; cin>>n; while (n--) { cin>>m; for (i = 0; i < m; ++i) cin>>str[i]; solve(); } return 0;}