题目链接：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即为问题的解。
#include <iostream>
#include <string.h>
using namespace std;
const int maxn = + ; // 碱基序列数的上限
const int maxs = + ; // 串长上限 int main()
{
char p[maxn][maxs], ans[maxs], s[maxs];
int i, j, k, len, maxlen, m, n;
while (scanf("%d", &n) != EOF)
{
while (n--)
{
memset(ans, , sizeof(ans)); // 最长公共子串
scanf("%d", &m); // 输入碱基序列的数目
for (i = ; i < m; i++) // 输入第i个碱基序列
scanf("%s", p[i]);
len = strlen(p[]);
maxlen = ; // 最长公共子串的长度
for (i = ; i < len; i++) // 枚举p[0]的每个子串，判断其是否为目标子串，子串的起始位置为i，结束位置为j
{
for (j = i+; j < len; j++)
{
strncpy(s, p[]+i, j-i+); // 提取该子串s(即长度为j-i+1，p[0]+i的所有字符复制到s中
s[j-i+] = '\0';
bool ok = true;
for (k = ; ok && k < m; k++)
{
if (strstr(p[k], s) == NULL) // 试探s是否为p[1]...p[m-1]的公共子串
{
ok = false;
break;
}
}
if (ok && (j-i+ > maxlen || maxlen == j-i+ && strcmp(ans, s) > )) // 若s是目前最长的公共子串，或者虽然s同属最长公共子串但字典序小，则s设为最长公共子串
{
maxlen = j-i+;
strcpy(ans, s);
}
}
}
if (maxlen < ) // 若最长的公共子串的长度不足3，则给出错误信息，否则输出最长公共子串
{
printf("no significant commonalities\n");
}
else
printf("%s\n", ans);
}
}
return ;
}