黑马程序员技术交流社区

标题: 如何求出多个字符串的公共子串 [打印本页]
作者: keycola    时间: 2014-12-10 15:26
标题: 如何求出多个字符串的公共子串
如何求出多个字符串的公共子串

如 abcdef
     defkg

公共子串就是 def
作者: young_star    时间: 2014-12-10 15:37
  1. #include<stdio.h>
  2. #include<string.h>

  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;

  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. }
复制代码
作者: arui12580    时间: 2014-12-10 15:49
那个，这是LCS算法问题。。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2