注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

还东国的博客

行之苟有恒,久久自芬芳

 
 
 

日志

 
 

(转载)阿里笔试之最长公共子串  

2015-08-20 16:42:17|  分类: 基本知识 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

发现真得有人的想法相当的棒,非常值得学习和借鉴。如下面这个方法,简单有效。

阿里笔试之最长公共子串

http://www.360doc.com/content/15/0818/10/7673502_493169010.shtml

题目描述:给定一个query和一个text,均由小写字母组成。要求在text中找出以同样的顺序连续出现在query中的最长连续字母序列的长度。例如,query“acbac”text“acaccbabb”,那么text中的“cba”为最长的连续出现在query中的字母序列,因此,返回结果应该为其长度3。请注意程序效率。

思路:用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1序列,其对应的位置就是最长匹配子串的位置.

当字符匹配的时候,不是简单的给相应元素赋上1,而是赋上其左上角元素的值加1。我们用两个标记变量来标记矩阵中值最大的元素的位置,在矩阵生成的过程中来判断当前生成的元素的值是不是最大的,据此来改变标记变量的值,那么到矩阵完成的时候,最长匹配子串的位置和长度就已经出来了。

实例如下:

     a    c    b    a    c

a   1    0    0    1    0   

c   0    2    0    0    2

a   1    0    0    1    0

c   0    2    0    0    2

c   0    1    0    0    1

b   0    0    2    0    0

a   1    0    0    3    0    

b   0    0    1    0    0

b   0    0    1    0    0

(红色为最长公共子串)

?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

#include <cstring>

#include <cstdio>

#define M 1010

int LCS(char query[], char text[])

{

int len_query=strlen(query),len_text=strlen(text);

//数组c记录匹配情况,模拟二维矩阵

char c[len_text];

int len, i, j;

len=0;

for(i=0; i<len_query; i++)

{

//不反过来会把之前数组元素冲掉的,因为后面的元素需要根据前面的元素计算

for(j=len_text-1; j>=0; j--)

{

if(query[i] == text[j])

{

if(i==0 || j==0)

c[j]=1;

else

c[j]=c[j-1]+1;

}

else

c[j] = 0;

if(c[j] > len)

len=c[j];

}

}

return len;

}

int main()

{

char str1[M],str2[M];

printf("请输入字符串query:");

scanf("%s", str1);

printf("请输入字符串text:");

scanf("%s", str2);

printf("所求长度为:");

printf("%d\n",LCS(str1,str2));

return 0;

}

 说明一下上面的原理,看下面的表:

1

1

0

0

0

1

0

0

0

0

2

0

0

0

2

0

0

0

0

3

0

0

0

0

这个表很明显是模拟上面的矩阵的,

第一,为什么要倒着查,上面也提到了,是防止把使用的数据给冲掉。同时为了模拟加左上角。大家看,三行如果全成一行,会不会是c[j] = c[j-1] + 1;这是不是就是加了矩阵的左上角那个值。

第二,为什么是一个一维数组来模拟矩阵,因为第一的原因,数据在使用后就可以置0了,也就是说,把上面三行全成一行,然后去除没用的前两行(N-1)行,你就会发现只余下最大的了。

所以说,有一些东西看似复杂,其实化简成简单的还是会更让人明白。

  评论这张
 
阅读(257)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017