黑马程序员技术交流社区

标题: 找出多个字符串中的最大公共子字符串 [打印本页]
作者: xiedongjiao    时间: 2015-3-19 13:51
标题: 找出多个字符串中的最大公共子字符串
题目：找出多个字符串中的最大公共子字符串，如“nbitheimanb”和“itheia”的最大子串是：”ithei”。（C语言）
感觉自己的这种方法挺麻烦，以下是代码，求交流！

  2. <P> #include <stdio.h>
  3. #include <string.h>
  4. char res1[100] = "", res2[100] = "";</P>
  5. <P>char *fun(char * str1, char * str2)
  6. {
  7. int i,j,k;
  8. int point = 1;//用于标记公共字符串的存储位置
  9. for(i=0;i<strlen(str1);i++)
  10. {
  11.   k = i;
  12.   for(j=0;j<strlen(str2);j++)
  13.   {
  14.    if(str1[k] == str2[j])
  15.    {
  16.     if(point == 1)
  17.     {
  18.      strncat(res1, &str1[k], 1);
  19.      k++;
  20.     }
  21.     else
  22.     {
  23.      strncat(res2, &str1[k], 1);
  24.      k++;
  25.     }
  26.    }
  27.    else
  28.    {
  29.     if(strlen(res1)<strlen(res2))
  30.     {
  31.      memset(res1,0,100);
  32.      point = 1;
  33.     }
  34.     else
  35.     {
  36.      memset(res2,0,100);
  37.      point = 2;
  38.     }
  39.    }
  40.   }
  41.   if(strlen(res1)<strlen(res2))
  42.   {
  43.    memset(res1,0,100);
  44.    point = 1;
  45.   }
  46.   else
  47.   {
  48.    memset(res2,0,100);
  49.    point = 2;
  50.   }
  51. }

  53. if((strlen(res1)==strlen(res2))&&(!strlen(res1)))
  54. {
  55.   printf("无公共字符串\n");
  56.   return NULL;
  57. }
  58. if(strlen(res1)<strlen(res2))
  59.   return res2;
  60. else
  61.   return res1;
  62. }
  63. int main()
  64. {
  65. char string1[100] = "", string2[100] = "", string3[100] = "";
  66. printf("请输入三个字符串\n");//仅以三个字符串代表多个字符串
  67. scanf("%s %s %s", string1, string2, string3);
  68. char *result;
  69. result = fun(string1, string2);
  70. if(result != NULL)
  71. {
  72.   result = fun(result, string3);
  73.   if(result!=NULL)
  74.    printf("%s\n", result);
  75. }
  76. return 0;
  77. }</P>
复制代码

作者: wenfeng340    时间: 2015-3-19 14:36
这是我做基础测试的时候做的

  1. #include <stdio.h>
  2. #include <string.h>
  3. #define N 2
  4. #define MAXLEN 100

  6. void main()
  7. {
  8.     char note[20];
  9.     int maxLen = MAXLEN;
  10.     char *pStr[N],pStr1[N][MAXLEN];
  11.     int i,j,k,min,maxlen= 0;
  12.     char maxStr[MAXLEN],*tmpStr,*temp,temp1[MAXLEN];
  13.         int len,len0,n1;
  14.         n1=N;
  15.         sprintf(note,"请输入%d个字符串",n1);
  16.         printf("%s\n",note);
  17.    
  18.     //找出输入的字符串中长度最小的串，并把最小串序号记在min中
  19.     for(i = 0; i < N; i++){
  20.         gets(pStr1[i]);
  21.                 pStr[i]=pStr1[i];
  22.         len = strlen(pStr[i]);
  23.         if(len < maxLen){
  24.             maxLen = len;
  25.             min = i;
  26.         }
  27.     }
  28.         //把最小的字符串放到第一个位置
  29.     temp = pStr[0];
  30.     pStr[0] = pStr[min];
  31.     pStr[min] = temp;

  33.     len0 = strlen(pStr[0]);
  34.     for(i = 0; i < len0 ; i++)
  35.     {
  36.         for(j = 0; j < len0 ; j++)
  37.         {
  38.                         memset(temp1,0,MAXLEN);
  39.                         for(int n=0;n<=len0-j-i-1;n++) //求出第一个字符串的子字符串
  40.                         {
  41.                                 temp1[n]=pStr[0][i+n];
  42.                         }
  43.             tmpStr = temp1;
  44.                         if(strlen(tmpStr)<1)
  45.                                         continue;
  46.             for(k = 1; k < N; ++k)
  47.             {
  48.                 if(strstr(pStr[k],tmpStr) == NULL)
  49.                     break;
  50.                 else
  51.                     continue;
  52.             }
  53.             if(k == N)
  54.             {
  55.                 if(strlen(tmpStr) > maxlen)
  56.                 {
  57.                                         memset(maxStr,0,MAXLEN);
  58.                     maxlen = strlen(tmpStr);
  59.                                         for(int v=0;v<strlen(tmpStr);v++)
  60.                                         {
  61.                                                 maxStr[v]=tmpStr[v];
  62.                                         }
  63.                 }
  64.             }
  65.         }
  66.     }
  67.     printf("最大公共子串为：");
  68.     printf("%s",maxStr);
  69.         getchar();
  70. }
复制代码







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