黑马程序员技术交流社区

标题: 找出多个字符串中的最大公共子字符串 [打印本页]

---

作者: 花轮    时间: 2014-12-18 14:13
标题: 找出多个字符串中的最大公共子字符串
这道题，一个亲提示后，我百度了一下，据说是微软面试题。。基础测试不造为毛要考
lcs算法

1. #include<stdio.h>
   
2. #include<string.h>
   
3. voidmain()
   
4. {
   
5.         char *x="aabcdababce";
   
6.         char *y="12abcabcdace";
   
7.         int m=strlen(x);
   
8.         int n=strlen(y);
   
9.         int i,j,k,l;
   
10.         int maxlength=0;
    
11.         int start=0;
    
12.         int count=0;//用来判断是否匹配的变量
    
13.         for(i=1;i<=n;i++)//匹配长度的循环
    
14.         for(j=0;j<n-i+1;j++)//y的起始位置的循环
    
15.         for(k=0;k<m-i+1;k++)//x的起始位置的循环
    
16.         {
    
17.                 count=0;
    
18.                 for(l=0;l<i;l++)//判断是否匹配,代码可以优化
    
19.                 if(y[j+l]==x[k+l])
    
20.                 count++;
    
21.                 if(count==i&&i>maxlength)
    
22.                 {
    
23.                         maxlength=i;//记录最大长度
    
24.                         start=j;//记录最大长度的起起位置
    
25.                 }
    
26.         }
    
27.         if(maxlength==0)
    
28.         printf("NoAnswer");
    
29.         else
    
30.         for(i=0;i<maxlength;i++)
    
31.         printf("%c",y[start+i]);
    
32. }

复制代码

这是百度大神百科出来的，我表示接受无能。
又找到了几篇博客，原理是两个字符串一个做行一个做列，组成个矩形进行比较。相同的置1，不同的置0
"nbitheimanb”和“itheia
      n   b   i   t   h   e    i   m   a   n   b
i     0   0  1  0   0    0   1   0    0   0   0
t    0    0  0  1   0    0   0   0    0   0   0
h   0    0  0  0   1    0   0   0    0   0   0
e   0   0   0   0   0   1   0    0   0   0   0
i    0   0   1   0   0    0   1   0    0   0  0
a    0   0  0   0   0    0   0   0    1   0   0


可是如果只置1的话要查找也很麻烦，所以大神们又想出来了优化。如果两个字符相同的话，就把他左上角的数字加1
      n   b   i   t   h   e    i   m   a   n   b
i     0   0  1  0   0    0   1   0    0   0   0
t    0    0  0  2   0    0   0   0    0   0   0
h   0    0  0  0   3   0   0   0    0   0   0
e   0   0   0   0   0   4   0    0   0   0   0
i    0   0   1   0   0   0   5   0    0   0  0
a    0   0  0   0   0   0   0   0    1   0   0



大家可以根据这个思路试着写一下。

---

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

黑马程序员IT技术论坛 X3.2