poj 3080 Blue Jeans（KMP匹配，枚举子串）

本文主要是介绍poj 3080 Blue Jeans（KMP匹配，枚举子串），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：

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];
int  f[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;
}

 ——  生命的意义，在于赋予它意义士。

          原创 http://blog.csdn.net/shuangde800 ， By   D_Double  (转载请标明)

这篇关于poj 3080 Blue Jeans（KMP匹配，枚举子串）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---