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

1. http://bbs.itheima.com/thread-178570-1-1.html

复制代码

先上暴击搜索算法、注释以加。由于是在Xcode下写的，文件也是用.m所以就用#import预处理指令

1. 
   
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. }
    
16. 
    
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. }
    

复制代码

#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]);
}
}

这有两种方式，一种是暴力枚举，一种是动态规划，现在在床上，用手机不方便，明天贴代码。

梅西 发表于 2015-3-20 00:46
#include
#include

干么把那么大的数组放在栈区，写成全局变量比较好。个人意见既然你写了动态规划，你就解释下……。提问的人很可能没参加过算法竞赛可能根本就不懂。

sixleaves 发表于 2015-3-20 00:52
干么把那么大的数组放在栈区，写成全局变量比较好。个人意见既然你写了动态规划，你就解释下……。提问的 ...

好嘛！！！

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

是暴力搜索、打错

如果不算算strstr的时间复杂度、则整个算法的时间复杂度是O(n^2)。低效的算法、不可拥于交大的字符串、又耗内存。

梅西 发表于 2015-3-20 00:46
#include
#include

这里奖励的分少，请到http://bbs.itheima.com/thread-178570-1-1.html这里答题

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

这里奖励的分少，请到http://bbs.itheima.com/thread-178570-1-1.html这里答题

#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-20 00:46
#include
#include

这说你这个连个注释都没有是程序员之间的正常交流吗？

顶一下！！！