上次基础测试题，感觉这道题挺有意思的，自己也是做了老长时间，代码是这样的

1. //
   
2. //  main.m
   
3. //  测试题10
   
4. //
   
5. //  Created by Mike on 14-12-5.
   
6. //  Copyright (c) 2014年 Mike. All rights reserved.
   
7. //
   
8. 
   
9. /*
   
10. 10、 找出多个字符串中的最大公共子字符串，如“nbitheimanb”和“itheia”的最大子串是：”ithei”。（C语言）
    
11. */
    
12. #import <Foundation/Foundation.h>
    
13. 
    
14. #define MAXLEN 80
    
15. char *maxCommon(char *s, char *t)
    
16. {
    
17.         char arr[MAXLEN][MAXLEN];//用arr存储所有的公共子串 arr[0]代表第一个子串
    
18.         int len[MAXLEN]; //用len[i]存储arr[i]串对应的长度
    
19.         int maxIndex,maxLen;//最长子串的索引maxIndex和最大长度maxLen
    
20.    
    
21.         int slen = 0;
    
22.         int tlen = 0;
    
23.         char *p = s;
    
24.         char *q = t;
    
25.    
    
26.         int i=0,j=0,countp=0;
    
27.         int counti;
    
28.     //计算s和t的长度 以串长短的为模式串
    
29.         while(*p)
    
30.         {
    
31.                 slen++;
    
32.                 p++;
    
33.         }
    
34.         p = t;
    
35.         while(*p)
    
36.         {
    
37.                 tlen++;
    
38.                 p++;
    
39.         }
    
40.         //p指向长的字符串q指向短的字符串
    
41.         if(slen<tlen)
    
42.         {
    
43.                 p = t;
    
44.                 q = s;
    
45.         }
    
46.         else
    
47.         {
    
48.                 p = s;
    
49.                 q = t;
    
50.         }
    
51.        
    
52.         //将全部的公共串存入arr[][]同时存入长度len[]
    
53.         while(*q)
    
54.         {
    
55.                 char *q1 = q;//q1为模式串 它是逐渐变化的如itheima->theima->heima->eima....
    
56.                 char *p1 =p; //p1为主串，在while(*p1)循环内部变化nbitheima->bitheima->itheima....
    
57.                 while(*p1)
    
58.                 {
    
59.                         if(*q1==*p1)
    
60.                         {
    
61.                                 arr[i][j] =*p1;len[i]++;
    
62.                                 j++;
    
63.                                 p1++;
    
64.                                 q1++;
    
65.                                
    
66.                                 if(!*q1)
    
67.                                 {
    
68.                                         arr[i][j]='\0';
    
69.                                         break;
    
70.                                 }
    
71.                                 if(!*p1)
    
72.                                 {
    
73.                                         arr[i][j]='\0';
    
74.                                 }
    
75.                         }
    
76.                         else
    
77.                         {
    
78.                                 q1 =q;
    
79.                                 if(j!=0)//如果a[i]已经存入公共串
    
80.                                 {
    
81.                                         arr[i][j]='\0';
    
82.                                         i++;j=0;
    
83.                                 }
    
84.                                 p1 = p+(++countp);
    
85.                                 while(*p1&&*q1!=*p1)//如果总是q1!=*p1 不断改变主串nbitheima->bitheima->itheima....
    
86.                                 {
    
87.                                         p1 = p+(++countp);
    
88.                                         //printf("p1=%s\n",p1);
    
89.                                 }
    
90.                         }
    
91.             
    
92.                 }
    
93.                 i++;
    
94.                 j=0;
    
95.                 //printf("-------------------------------------------\n");
    
96.                 countp = 0;
    
97.                 q++;
    
98.         }
    
99.    
    
100.         //得到最大串长对应的串序号
     
101.         for(counti = 0;counti<i;counti++)
     
102.         {
     
103.                 if(len[counti]>maxLen)
     
104.                 {
     
105.                         maxLen =len[counti];
     
106.                         maxIndex = counti;
     
107.                 }
     
108.         }
     
109.         return arr[maxIndex];
     
110. }
     
111. int main()
     
112. {
     
113.         printf("最长公共子串是：%s\n",maxCommon("nbitheimanb","itheima"));
     
114.         return 0;
     
115. }
     

复制代码

感觉这样的话效率很低，想问一下有没有好的算法。

这题我也有 顶一下

厉害！！！！我还没看到import

度娘有更神奇的算法

厉害！！！！！11

我没有用数组去存储匹配到的每一个字符串，我只是用了一个指针将每次匹配到的第一个字符的地址保存到指针中，感觉这样可以少分写空间，再用一个整形变量去保存最大长度，最后通过p[n]的形式取出匹配到的字符串

1. //3.定义一个求最大公共子字符串的函数
   
2. void maxChild(char str[],char str1[])
   
3. {
   
4.     //4.定义两个指针变量，用于记录相同的起始地址
   
5.     char *p,*q;
   
6.    
   
7.     //5.定义两个整型变量，用于保存最大公共长度
   
8.     int n=0,m=0;
   
9.    
   
10.     //6.通过for循环来遍历第一个字符串
    
11.     for(int i=0;i<strlen(str);i++)
    
12.     {
    
13.         //7.通过for循环遍历第二个字符串
    
14.         for(int j=0;j<strlen(str1);j++)
    
15.         {
    
16.             //8.每次比较完两个字符串的公共部分后，都设置m=0
    
17.             m = 0;
    
18.             //9.判断两个字符串起始相同，只要一有相同的，就同步进行判断
    
19.             if(str[i]==str1[j]&&str1[j]!='\0'){
    
20.                 //10.通过同步进行比较公共字符串
    
21.                 for(int k=0;str[k+i]!='\0'&&str1[k+j]!='\0'&&str[k+i]==str1[k+j];k++)
    
22.                 {
    
23.                     //11.记录公共字符个数和第一个匹配的地址
    
24.                     m++;
    
25.                     p = &str[i];
    
26.                 }
    
27.                 if(m>n)
    
28.                 {
    
29.                     //12.保存大地址，和最大个数
    
30.                     q = p;
    
31.                     n = m;
    
32.                 }
    
33.             }
    
34.         }
    
35.     }
    
36.    
    
37.     //13.判断是否有公共子字符串
    
38.     if(n>0){
    
39.         //14.进行输出最大公共子字符串
    
40.         for(int i=0;i<n;i++){
    
41.             printf("%c",*(q+i));
    
42.         }
    
43.     }else{
    
44.         printf("没有公共子字符串");
    
45.     }
    
46. }
    

复制代码

数据结构里有个：kmp 匹配算法。可以看看~

饶世红 发表于 2014-12-17 13:15

你好 你发的这个题目我也有，试了下 完美运行！感谢！
但是其中一个变量我没搞懂。想麻烦你解释一下。就是：                if(m>n)
                {
                    //12.保存大地址，和最大个数
                    q = p;
                    n = m;
                }
其中的q不是应该保存最大的地址吗?也就是最大的公共字符串的最后一个字符的地址，但是我看你这是保存的最大公共字符串的头一个的地址。我肯定有哪里理解错了，麻烦大神给我指点迷津啊。我QQ1026238004，不胜感激！！！

饶世红 发表于 2014-12-17 13:15

你好 你发的这个题目我也有，试了下 完美运行！感谢！
但是其中一个变量我没搞懂。想麻烦你解释一下。就是：                if(m>n)
                {
                    //12.保存大地址，和最大个数
                    q = p;
                    n = m;
                }
其中的q不是应该保存最大的地址吗?也就是最大的公共字符串的最后一个字符的地址，但是我看你这是保存的最大公共字符串的头一个的地址。我肯定有哪里理解错了，麻烦大神给我指点迷津啊。我QQ1026238004，不胜感激！！！

1026238004 发表于 2015-2-1 15:52
你好 你发的这个题目我也有，试了下 完美运行！感谢！
但是其中一个变量我没搞懂。想麻烦你解释一下。就 ...

1. p = &str[i];

复制代码

   你应该是这句看错了，在那个for循环里i并没有自加，自加的是k

1026238004 发表于 2015-2-1 15:52
你好 你发的这个题目我也有，试了下 完美运行！感谢！
但是其中一个变量我没搞懂。想麻烦你解释一下。就 ...

1. for(int k=0;str[k+i]!='\0'&&str1[k+j]!='\0'&&str[k+i]==str1[k+j];k++)
   
2.                 {
   
3.                     //11.记录公共字符个数和第一个匹配的地址
   
4.                     m++;
   
5.                     // p = &str[i];  放到下面会更好
   
6.                 }
   
7. p = &str[i];

复制代码

钟楼上的猫 发表于 2015-2-2 10:44
你应该是这句看错了，在那个for循环里i并没有自加，自加的是k

i+k又没给i赋值。。。orz

钟楼上的猫 发表于 2015-2-2 10:53

论坛不能直接发出      ,要点插入代码才行  我已经改了

饶世红 发表于 2014-12-17 13:15

怎么链接代码。。。谢楼主分享

学习了...

厉害！！！！！

我也有这个题目，顺便来看看 赞一个

高手啊。。。

赞一个，百度到你了  哈哈