题目链接：http://poj.org/problem?id=3080
该题属于字符串处理中的串模式匹配问题。题目要求我们：给出一个DNA碱基序列，输出最长的相同的碱基子序列。（保证在所有的序列中都有出现）
这里采用了Brute Force算法（由于碱基序列的串长仅为60，规模比较小），这是模式匹配的一种最简单的做法。
设： 最长公共字串为ans，其长度为maxlen。
m个碱基序列为p[0]...p[m-1]。由于公共子序列是每个碱基序列的子串，因此不妨枚举p[0]的每一个可能的子串s。以s为模式，分别以p[1]...p[m-1]为目标进行匹配计算：
若s为p[1]...p[m-1]的公共子串（strstr(p[k], s) != NULL, 1 <= k <= m-1），且s串的长度>maxlen，或者s的长度虽等于maxlen，但字典序小于目前最长的公共子串ans（strcmp(ans, s) > 0），则将s调整为最长公共子串（maxlen = s串的长度; strcpy(ans, s)）。在枚举了p[0]的所有子串与p[1]...p[m-1]后，最终得出的最长公共子串ans即为问题的解。
1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 const int maxn = 10 + 5; // 碱基序列数的上限 5 const int maxs = 60 + 5; // 串长上限 6 7 int main() 8 { 9 char p[maxn][maxs], ans[maxs], s[maxs]; 10 int i, j, k, len, maxlen, m, n; 11 while (scanf("%d", &n) != EOF) 12 { 13 while (n--) 14 { 15 memset(ans, 0, sizeof(ans)); // 最长公共子串 16 scanf("%d", &m); // 输入碱基序列的数目 17 for (i = 0; i < m; i++) // 输入第i个碱基序列 18 scanf("%s", p[i]); 19 len = strlen(p[0]); 20 maxlen = 0; // 最长公共子串的长度 21 for (i = 0; i < len; i++) // 枚举p[0]的每个子串，判断其是否为目标子串，子串的起始位置为i，结束位置为j 22 { 23 for (j = i+2; j < len; j++) 24 { 25 strncpy(s, p[0]+i, j-i+1); // 提取该子串s(即长度为j-i+1，p[0]+i的所有字符复制到s中
26 s[j-i+1] = '\0'; 27 bool ok = true; 28 for (k = 1; ok && k < m; k++) 29 { 30 if (strstr(p[k], s) == NULL) // 试探s是否为p[1]...p[m-1]的公共子串
31 { 32 ok = false; 33 break; 34 } 35 } 36 if (ok && (j-i+1 > maxlen || maxlen == j-i+1 && strcmp(ans, s) > 0)) // 若s是目前最长的公共子串，或者虽然s同属最长公共子串但字典序小，则s设为最长公共子串
37 { 38 maxlen = j-i+1; 39 strcpy(ans, s); 40 } 41 } 42 } 43 if (maxlen < 3) // 若最长的公共子串的长度不足3，则给出错误信息，否则输出最长公共子串
44 { 45 printf("no significant commonalities\n"); 46 } 47 else 48 printf("%s\n", ans); 49 } 50 } 51 return 0; 52 }