A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© Mike_zh 中级黑马   /  2014-12-17 00:40  /  12718 人查看  /  25 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

上次基础测试题,感觉这道题挺有意思的,自己也是做了老长时间,代码是这样的
  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、 找出多个字符串中的最大公共子字符串,如“nbitheimanb”和“itheia”的最大子串是:”ithei”。(C语言)
  10. */
  11. #import <Foundation/Foundation.h>

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

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

25 个回复

倒序浏览
花轮 来自手机 中级黑马 2014-12-17 01:48:49
沙发
这题我也有 顶一下
回复 使用道具 举报
厉害!!!!我还没看到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. }
复制代码
回复 使用道具 举报 1 0
数据结构里有个:kmp 匹配算法。可以看看~
回复 使用道具 举报

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

你好 你发的这个题目我也有,试了下 完美运行!感谢!
但是其中一个变量我没搞懂。想麻烦你解释一下。就是:                if(m>n)
                {
                    //12.保存大地址,和最大个数
                    q = p;
                    n = m;
                }
其中的q不是应该保存最大的地址吗?也就是最大的公共字符串的最后一个字符的地址,但是我看你这是保存的最大公共字符串的头一个的地址。我肯定有哪里理解错了,麻烦大神给我指点迷津啊。我QQ1026238004,不胜感激!!!
回复 使用道具 举报
本帖最后由 钟楼上的猫 于 2015-2-2 10:54 编辑
1026238004 发表于 2015-2-1 15:52
你好 你发的这个题目我也有,试了下 完美运行!感谢!
但是其中一个变量我没搞懂。想麻烦你解释一下。就 ...
  1. p = &str[i];
复制代码
   你应该是这句看错了,在那个for循环里i并没有自加,自加的是k

点评

就是这里 i+k不就是i的值吗  发表于 2015-2-2 11:16
回复 使用道具 举报
本帖最后由 钟楼上的猫 于 2015-2-2 10:55 编辑
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];
复制代码


点评

不对阿 p =&str后面有这个的[i]的值  发表于 2015-2-2 11:19
回复 使用道具 举报
钟楼上的猫 发表于 2015-2-2 10:44
你应该是这句看错了,在那个for循环里i并没有自加,自加的是k

i+k又没给i赋值。。。orz
回复 使用道具 举报

论坛不能直接发出      ,要点插入代码才行  我已经改了
回复 使用道具 举报

怎么链接代码。。。谢楼主分享
回复 使用道具 举报
学习了...
回复 使用道具 举报
厉害!!!!!
回复 使用道具 举报
我也有这个题目,顺便来看看 赞一个
回复 使用道具 举报
高手啊。。。
回复 使用道具 举报
赞一个,百度到你了  哈哈
回复 使用道具 举报
12下一页
您需要登录后才可以回帖 登录 | 加入黑马