学步园

题意： 输入M个定长为60的DNA序列（字符串），求M条DNA的最长公共子序列，若有最长的公共子序列有若干条，则输出字典序最小的。
显然是一个字符串匹配问题。第一次用KMP算法。幸好看了严蔚敏老师的数据结构视频（第11,12），讲的很细。
题解：需要注意输出字典序最小的模式序列

#include <stack>
#include <cstring>
#include <iostream>
using namespace std;
             
#define M 65
struct node { char str[M]; };
char DNA[15][M], res[M];
int next[M], n, m, flag;
stack<node> S;

void make_pattern ()  
{
	node temp;
	while ( ! S.empty() ) S.pop();
      /*  先从长度3开始枚举可能的模式序列，直至长度60，并存放入栈*/
	for ( int pl = 3; pl <= 60; pl++ )
        {
             for ( int i = 0; i <= 57; i++ )
             {
                  if ( i + pl >  60 )
                      break;
                  strncpy(temp.str,DNA[0]+i,pl);
                  temp.str[pl] = '\0';
                  S.push(temp);
             }
        }
}

void get_Next ( char p[] )   //数组可以进一步优化，但是现在懒得写了
{
    next[0] = -1;
    int i = 0, j = -1, len=strlen(p);
    while ( i < len )
   {
        if ( j == -1 || p[i] == p[j] )
        {++i; ++j;next[i] = j;}
        else j = next[j];
    }
}

/*检测某一模式序列是否是所有DNA的公共子序列,函数返回布尔值*/
bool KMP ( char p[] )
{
    get_Next(p);
    int i,j,k,len=strlen(p);
    for ( k = 1; k < m; k++ )
    {
         i = j = 0;
         while ( i < 60 && j < len )
        {
             if ( j == -1 || DNA[k][i] == p[j] )
             { ++i; ++j; }
             else
             { j = next[j];};
        }
        if ( j < len )
             return false;
     }
     /*进行到这一步说明模式序列P是所有DNA的公共子序列*/
     if ( strcmp(p,res) < 0 || res[0] == '\0' )
     /*比较P与原来的结果，取字典序小的*/
          strcpy(res,p);
     return true;
}

int main()
{
    scanf("%d",&n);
    while ( n-- )
    {
         scanf("%d",&m);
         for ( int i = 0; i < m; i++ )
         scanf("%s",&DNA[i]);   
         res[0] = '\0';
         flag = false;
         make_pattern();
         while ( ! S.empty() ）
        { 
             node pat;
             pat = S.top(); S.pop();
             if ( flag ) 
            {
   /*flag=true说明已经匹配到公共子序列，即已经产生了一个可行的结果。若当前的模式序列pat.str长度小于已求出的的结果，
则可以跳出循环了，因为子序列入栈时是从短到长，所以出栈是从长到短，后面的长度一定更小。否则继续匹配，检测是否有字典序较小的*/  
	         if ( strlen(pat.str) < strlen(res) )
                     break;
                 else KMP(pat.str);
             } 
             else flag = KMP (pat.str);
        }
        if( flag )
            printf("%s\n", res);
        else
            printf("no significant commonalities\n"); 
 }
return 0;
}