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 (转载请标明)