本文共 1197 字，大约阅读时间需要 3 分钟。
POJ 3080，题目链接http://poj.org/problem?id=3080
题意：
就是求m个长度为60的字符串的最长连续公共子串，2<=m<=10
规定：
1、最长公共串长度小于3输出no significant commonalities
2、若出现多个等长的最长的子串，则输出字典序最小的串
思路：
1. 求公共最小连续子串，那么先把第一个串长度>=3的所有连续子串找出来，然后由短到长查看所有主串是否有该子串。
2. 如果发现一个公共子串，那么就开始找长度+1的公共子串；如果指定长度的所有子串都找不出一条是共有的，那么-1长度就是最长的公共子串。
例：长度为3的子串匹配时，当发现第一个长度为3的公共子串，则开始找长度为4的子串，如果发现第一个长度为4的子串，则开始找长度为5的子串，如果没有找到长度为5的公共子串，那么他们的最长公共子串长度就为4，此时就在长度为4的所有子串中，找出字典排序在前的。（暴力~）
代码：
//680K 32MS#include #include #include #include using std::string;using std::vector;#define DNA_Len 60bool BMSearch(const char* s, const char* t){ const char *p = strstr(s, t); if (p) return true; else return false;}int main(){ char temp[DNA_Len+1]; vector subStr[DNA_Len+1]; // 3-60 int caseNum; scanf("%d",&caseNum); while (caseNum-- > 0) { int deqNum;//2 <= m <= 10 scanf("%d", &deqNum); char **p = new char*[deqNum]; for (int i=0; i = 3){ //多个最长子串 按照字典排序 int len = strlen(temp); vector multiString; bool searched; for (int i=0,count=subStr[len].size(); i 0){ strcpy(temp, multiString.at(i).c_str()); } } printf("%s\n", temp); } else { printf("no significant commonalities\n"); } for (int i=0; i
转载地址：http://omtpi.baihongyu.com/