黑马程序员技术交流社区

标题: 基础测试题最后一道有点疑问，求解疑！ [打印本页]

作者: 花轮 时间: 2014-12-17 16:59
标题: 基础测试题最后一道有点疑问，求解疑！
找出多个字符串中的最大公共子字符串，如“nbitheimanb”和“itheia”的最大子串是：”ithei”
这题是不是要把第一个字符串中第一个字符取出来和第二个中每个进行对比，然后第一个字符串中第二个字符取出来和第二个每个进行对比，然后一直比到第一个字符串和第二个中所有的比完，再计算哪段最长？？？晕，我思路对不对啊。。。

作者: wangxiaoit 时间: 2014-12-17 17:11
思路差不多，就是这样比较，但可以再想想换个简单方法。我是这么想的，你看看行不行。先从短字符串中取子字符串，跟长字符串进行比较看是否存在，关键在取子串上，我们应该从最大长度开始取，循环越取越短。这样一旦比较成功，返回的字符串就是最长的公共子串，就不需要计算哪段长了。比如说短的字符串是 “abcd”我们取子串顺序："abcd","abc","bcd","ab","bc","cd",.....等。

作者: 花轮 时间: 2014-12-17 17:15

wangxiaoit 发表于 2014-12-17 17:11
思路差不多，就是这样比较，但可以再想想换个简单方法。我是这么想的，你看看行不行。先从短字符串中取子字 ...

这个好！赞一个！

作者: wangxiaoit 时间: 2014-12-17 17:18

花轮发表于 2014-12-17 17:15
这个好！赞一个！

印象中老师某个视频里这样讲过。。。努力回忆了下。你在做基础测试题吗？

作者: 花轮 时间: 2014-12-17 17:19

wangxiaoit 发表于 2014-12-17 17:18
印象中老师某个视频里这样讲过。。。努力回忆了下。你在做基础测试题吗？ ...

对啊，就这最后一道了

作者: 从今以后 时间: 2014-12-17 17:33
听人说才知道这叫LCS算法= =可以弄个二维数组，a[i][j]，全部置0，两个字符串一个当行一个当列，遍历，相同字符标记为1，且等于左上角那个元素值+1，不同则啥不做还是为0，最后最长的对角线就是那个最长子串。像这样：
  n b i  t h e  i m a n b （列 j）
i 0 0 1 0 0 0 1 0  0 0 0
t 0 0 0 2 0 0 0 0  0
h          3
e             4
i                5
a                   0
（行 i）
最高加到了5，说明这就是最长的，在遍历的时候记下5这个位置下标比如i，那么ithei这个串下标i到前面5个元素就是那个子串了。= =

作者: 花轮 时间: 2014-12-17 17:39

从今以后发表于 2014-12-17 17:33
听人说才知道这叫LCS算法= =可以弄个二维数组，a[j]，全部置0，两个字符串一个当行一个当列，遍历，相同字 ...

LCS算法..百度了一下出来了好多，这个方法很好哎，点个赞~我去试试

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

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