算法题：poj 3080 Blue Jeans（KMP匹配，枚举子串）

算法题：poj 3080 Blue Jeans（KMP匹配，枚举子串）2014-03-17 csdn博客 shuangde800链接：

http://poj.org/problem？id=3080

题目大意：

给出m（2<=m<=10）个DNA序列，求出这m个序列中最长的公共字串。如果有多个相同长度的，输出字典序最小的。

分析与总结:

依次枚举所有的子串，然后再看是否在所有序列中都能够匹配。保存下长度最大且字典序最小的序列。

代码：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 1000005;const int N = 60;int nMax;char seq[12][85];char ans[85];intf[85];void getFail（char *p, int *f）{int m=strlen（p）;f[0]=f[1]=0;for（int i=1; i<m; ++i）{int j=f[i];while（j && p[i]！=p[j]）j=f[j];f[i+1] = p[i]==p[j]？1+j:0;}}bool find（char *T,char *p,int *f）{getFail（p,f）;int n=strlen（T）;int m=strlen（p）;int j=0;for（int i=0; i<n; ++i）{ while（j && T[i]！=p[j]）j=f[j]; if（T[i]==p[j]）++j; if（j==m）{ return true; }}return false;}int main（）{int nCase, m;char str[85];scanf（"%d",&nCase）;while（nCase--）{scanf（"%d",&m）;for（int i=0; i<m; ++i）{scanf（"%s",seq[i]）;}bool ok=false;nMax=3;// 枚举所有子串for（int i=0; i<m; ++i）{for（int j=0; j<N-3; ++j）{ //枚举起点memset（str, 0, sizeof（str））;for（int k=j,p=0; k<N; ++k）{str[p++]=seq[i][k];if（p>=nMax）{bool flag=false;for（int l=0; l<m; ++l）if（l！=i）{if（！find（seq[l],str,f））{flag=true;break;}}if（！flag）{if（p==nMax）{if（！ok）{ok=true;strcpy（ans,str）;}else if（strcmp（ans,str）>0）{strcpy（ans,str）;}}else if（p>nMax）{nMax=p;strcpy（ans,str）;}}else{break;// 如果这个长度不能匹配了，那么更长的也全部都不能匹配}}}}}if（ok）puts（ans）;else puts（"no significant commonalities"）;}return 0;}