如何求出多个字符串的公共子串

如 abcdef
     defkg

公共子串就是 def

1. #include<stdio.h>
   
2. #include<string.h>
   
3. 
   
4. void main()
   
5. {
   
6. char  a[500],b[500];
   
7. int array[500][500];
   
8. int aLen,bLen;
   
9. int i,j,max,m,n;
   
10. printf("请输入第一个字符串：");
    
11.     while(scanf("%s",&a)!=EOF)   //如果成功
    
12.         {
    
13.       printf("请输入第二个字符串：");
    
14.       scanf("%s",&b);
    
15.       aLen=strlen(a);
    
16.       bLen=strlen(b);
    
17.       for(i=0;i<bLen+1;i++)
    
18.       array[i][0]=0;
    
19.       for(i=0;i<aLen+1;i++)
    
20.       array[0][i]=0;
    
21.   
    
22.      for(i=1;i<=aLen;i++)         //二维数组赋值
    
23.          {
    
24.             for(j=1;j<=bLen;j++)     //i行j列
    
25.                 {
    
26.          if(a[i-1]==b[j-1])
    
27.                  {
    
28.             array[i][j]=array[i-1][j-1]+1;
    
29.                  }
    
30.          else
    
31.                  {
    
32.                     array[i][j]=0;
    
33. 
    
34.                  }
    
35.                 }
    
36.    
    
37.          }
    
38.    //输出公共字符串
    
39.          max=array[0][0];
    
40.          for(i=1;i<=aLen;i++)
    
41.          {
    
42.                  for(j=1;j<=bLen;j++)
    
43.                  {
    
44.            if(max<array[i][j])
    
45.                    {
    
46.                            max=array[i][j];
    
47.                            m=i;
    
48.                            n=j;
    
49.                    }
    
50.                  }
    
51.          }
    
52.          //printf("重复最大个数max:%d 行下标m: %d 列下标n:%d",max,m,n);
    
53.          printf("最大子串为：");
    
54.                   for(i=m-max;i<m;i++)
    
55.                  {
    
56.               printf("%c",a[i]);  
    
57.                  }
    
58.    
    
59.    printf("\n");
    
60. }
    
61. }

复制代码

那个，这是LCS算法问题。。