求多字符串的最长公共子串（POW）皇星客栈

求多字符串的最长公共子串（POW）

给定n个字符串，求这n个字符串的最长公共子串。例如给3个字符串：'abcb'、'bca'和'acbc'，则这三个字符串的最长公共子串即为'bc'。输入第一行为n，下面n行即为这n个字符串。输出它们的最长公共子串。

样例：

输入：

输出：

abcb

bca

acbc

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 
  4 char POW[200][200];
  5 char S[200];
  6 char T[200];
  7 int len[200];
  8 int nextval[256];
  9 int length_1;
 10 int ma;
 11 int length;
 12 int n;
 13 int ans; 
 14 
 15 void get_nextval( )
 16 {//求模式串Ｔ的next函数修正值并存入数组nextval.    
 17     int i=0;
 18     int j=1;
 19     int length;
 20     nextval[0]=-1;
 21     nextval[1]=0;
 22     length=strlen(T);
 23     
 24     while(j<length)
 25     {    
 26         if(i==-1||T[j]==T[i])
 27         {
 28             ++i;
 29             ++j;
 30             if(T[j]==T[i]) 
 31                 nextval[j]=nextval[i];
 32             else 
 33                 nextval[j]=i;
 34         }    
 35         else        
 36             i=nextval[i];
 37     } 
 38 /*    for( i=0; i<strlen(T);i++ )
 39         printf("%d ",nextval[i]);
 40     printf("\n");*/
 41 }
 42 
 43 void KMP( )
 44 {        
 45     int i;
 46     int j;
 47     int k;
 48     int m;
 49     ma=200;
 50     get_nextval( );
 51     for( k=1; k<n; k++ ) 
 52     {   
 53         i=0;
 54         j=0;
 55         m=0;
 56         while( j<length_1 && i < len[k] )
 57         {
 58             if( j==-1 || POW[k][i]==T[j] )    
 59             {    
 60                 ++i;    
 61                 ++j;            //继续比较后继字符    
 62             }    
 63             else          
 64                 j=nextval[j];  //模式串向后移动
 65             if( j>m )
 66                 m=j;
 67         }
 68         if( m<ma )
 69             ma = m;
 70     }
 71 }
 72 
 73 int main( )
 74 {    
 75     int i;
 76     int j;
 77     while( scanf("%d",&n) != EOF )    
 78     {    
 79         ans=0;
 80         for( i=0; i<n; i++ )
 81         {
 82             scanf("%s",POW[i]);
 83             len[i] = strlen(POW[i]);
 84         }
 85         for( i=0; i<len[0]; i++ )
 86         {
 87             strcpy(T,POW[0]+i);
 88             length_1 = len[0]-i;
 89             KMP( );
 90             if( ma > ans )
 91             {
 92                 ans = ma;
 93                 for( j=0; j<ans; j++ ) //记录公共子串
 94                     S[j] = T[j];
 95                 S[j] = '\0';
 96             }
 97         }
 98     //    printf("%d\n",ans);
 99         printf("%s\n",S);
100     }
101     return 0;      
102 }

求多字符串的最长公共子串（POW） 皇星客栈

求多字符串的最长公共子串（POW）

求多字符串的最长公共子串（POW）皇星客栈