黑马程序员技术交流社区

标题: 两个字符串中最大共公字符串奖技术分了 [打印本页]
作者: 恋梦    时间: 2015-3-20 00:38
标题: 两个字符串中最大共公字符串奖技术分了
本帖最后由 恋梦 于 2015-3-20 10:05 编辑

        如题，在截取两个字符串中最大共公字符串，c语言或oc都可以                例如字符串abcdefghijk和另一个字符串lmakfghmijlfg两个字符串中最大共公字符串是fgh
        奖励情况视答案方式奖，后面解法相同的即作废。
        这里奖励的分少，请到http://bbs.itheima.com/thread-178570-1-1.html这里答题
  1. http://bbs.itheima.com/thread-178570-1-1.html
复制代码


作者: sixleaves    时间: 2015-3-20 00:38
先上暴击搜索算法、注释以加。由于是在Xcode下写的，文件也是用.m所以就用#import预处理指令

  2. #import <stdio.h>
  3. #import <string.h>
  4. int findLCS(char *s1, char *s2, char **s, char **e);
  5. int main(int argc, const char * argv[]) {
  6.    
  7.     //  解法1 暴力枚举法(两个字符串),反复调用即可求多个。
  8.     char * s = NULL, *e = NULL;
  9.     char *s1 = "nbitheimanb", *s2 = "ithei";
  10.     findLCS(s1, s2, &s, &e);
  11.     for (char *p = s; p <= e; p++)
  12.         putchar(*p);
  13.     puts("");
  14.     return 0;
  15. }

  17. // 返回最大子串的大小，s记录最大子串的起始位置，e记录最后一个位置
  18. // 原本想用C++来写,比较简练，但是要求用C。
  19. int findLCS(char *s1, char *s2, char **s, char **e) {
  20.    
  21.     int len1 = strlen(s1), len2= strlen(s2);
  22.     char buf[100] = {0};
  23.     int max = -1;     // 记录最大子串的大小
  24.     char *str = NULL;
  25.     char *p = len1 > len2? s2 : s1;       // 指向两个串中最小串的第一个字符
  26.     if (p == s1)  str = s2; else str = s1;  // 最大子串肯定在最小两个串中，所以枚举它的位置进行判断即可。
  27.     for (char * ps = p; *ps; ps++) {
  28.         
  29.         for (char * pe = ps; *pe; pe++) {
  30.             
  31.             int len = pe - ps;  // 计算枚举的子串大小
  32.             strncpy(buf, ps, pe - ps);
  33.             
  34.             if (strstr(str, buf)) { // 查找是否存在该子串
  35.                
  36.                 if (len > max) {
  37.                     
  38.                     max = len;
  39.                     *s = ps;    // 记录新的最大子串起始位置
  40.                     *e = pe;    // 结束位置
  41.                 }
  42.             
  43.             }
  44.             
  45.             
  46.         }
  47.    
  48.     }
  49.     return max; // 返回最大子串大小。返回-1则不存在
  50. }
复制代码
作者: 梅西    时间: 2015-3-20 00:46
#include<stdio.h>
#include<string.h>

void main()
{
char  a[500],b[500];
int c[500][500];
int la,lb;
int i,j;
    while(scanf("%s",&a)!=EOF)
{
  scanf("%s",&b);
  la=strlen(a);
  lb=strlen(b);
  for(i=0;i<=lb;i++)
   c[i][0]=0;
  for(i=0;i<=la;i++)
   c[0][i]=0;
  
  for(i=1;i<=lb;i++)
   for(j=1;j<=la;j++)
   {
    if(a[j-1]==b[i-1])
    {
     c[j][i]=c[j-1][i-1]+1;
    }
    else
    {
     c[j][i]=c[j-1][i]>c[j][i-1]?c[j-1][i]:c[j][i-1];
    }
   }
   printf("%d\n",c[la][lb]);
}
}
作者: sixleaves    时间: 2015-3-20 00:46
这有两种方式，一种是暴力枚举，一种是动态规划，现在在床上，用手机不方便，明天贴代码。
作者: sixleaves    时间: 2015-3-20 00:52
梅西 发表于 2015-3-20 00:46
#include
#include


干么把那么大的数组放在栈区，写成全局变量比较好。个人意见既然你写了动态规划，你就解释下……。提问的人很可能没参加过算法竞赛可能根本就不懂。
作者: 梅西    时间: 2015-3-20 01:02
sixleaves 发表于 2015-3-20 00:52
干么把那么大的数组放在栈区，写成全局变量比较好。个人意见既然你写了动态规划，你就解释下……。提问的 ...

好嘛！！！
作者: sixleaves    时间: 2015-3-20 10:04
sixleaves 发表于 2015-3-20 10:02
先上暴击搜索算法、注释以加。由于是在Xcode下写的，文件也是用.m所以就用#import预处理指令
...

是暴力搜索、打错
作者: sixleaves    时间: 2015-3-20 10:07
如果不算算strstr的时间复杂度、则整个算法的时间复杂度是O(n^2)。低效的算法、不可拥于交大的字符串、又耗内存。
作者: 恋梦    时间: 2015-3-20 10:07
梅西 发表于 2015-3-20 00:46
#include
#include

这里奖励的分少，请到http://bbs.itheima.com/thread-178570-1-1.html这里答题
作者: 恋梦    时间: 2015-3-20 10:08
sixleaves 发表于 2015-3-20 10:02
先上暴击搜索算法、注释以加。由于是在Xcode下写的，文件也是用.m所以就用#import预处理指令
...

这里奖励的分少，请到http://bbs.itheima.com/thread-178570-1-1.html这里答题
作者: 261406938    时间: 2015-3-20 23:10
作者: 李大大    时间: 2015-3-22 23:00
#include<stdio.h>int main(){char str[200];    // 假定输入1行字符串，长度在200以内char s[20][16];   // 假定 用逗号分隔 的部分 约20个，每个长度 不超过16字符 double d[20];   // 假定数据个数 不超过 20 个int i,j=0,L,n=0;fgets(str,200,stdin);   // 读入一行 字符串，含换行符L = strlen(str);    //计算输入的字符串长度for (i=0;i<L;i++){s[n][j]=str[i]; j++;if (str[i]==','  || str[i]=='\n') {s[n][j-1]='\0'; j=0; n++;}   // 取出 逗号分隔 开的字符串}for (i=0;i<n;i++) printf("%s\n",s[i]);   //输出这些 分开的字符串 j=0;for (i=0;i<n;i++){if ( sscanf(s[i],"%lf",&d[j]) == 1) j++;    // 能转换为数的一个一个转换}printf("\n=======values========\n");for (i=0;i<j;i++) printf("%lf\n",d[i]);    // 输出这些数据return 0;}
作者: 小白一号    时间: 2015-3-23 21:35
梅西 发表于 2015-3-20 00:46
#include
#include

这说你这个连个注释都没有是程序员之间的正常交流吗？
作者: 向天笑    时间: 2015-3-28 17:22
顶一下！！！



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