如何输出两个字符串的最长公共字符串

最近在看《数据结构与算法JavaScript描述》这本书时,遇到了这个问题。结果我把代码复制到本地后,发现得不到正确的结果,于是对代码进行了改进。

function lcs(word1, word2) { 
word1 = '-' + word1;
word2 = '+' + word2;
var max = 0; 
var index = 0; 
var lcsarr = new Array(word1.length); 
for (var i = 0; i < lcsarr.length; i++) { 
    lcsarr[i] = new Array(word2.length); 
    for (var j = 0; j < lcsarr[0].length; j++) { 
        lcsarr[i][j] = 0; 
    } 
}
for (var i = 1; i < lcsarr.length; i++) { 
    for (var j = 1; j < lcsarr[0].length; j++) {            
        if (word1[i] == word2[j]) { 
            lcsarr[i][j] = lcsarr[i-1][j-1] + 1; 
        }
        if (max < lcsarr[i][j]) { 
            max = lcsarr[i][j]; 
            index = i; 
        }           
    } 
}    
return word1.slice(index+1-max,index+1);
}

不过此代码有缺陷,在最长公共字符串有多个的情况下,只能找到第一个。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,742评论 18 399
  • 第5章 引用类型(返回首页) 本章内容 使用对象 创建并操作数组 理解基本的JavaScript类型 使用基本类型...
    大学一百阅读 3,267评论 0 4
  • 控制台可能会输出以下警告信息 警告的原因: [UIImage imageNamed:nil] 警告的原因: [UI...
    船长_阅读 312评论 0 2
  • 第一次写,想给大家分享几个iOS项目中可能会使用到的小技巧 1、如何在app中打开设置中的app设置界面 网上有很...
    98k_sw阅读 868评论 0 1
  • 早上七点起床洗漱,大概七点二十分出发,到学校大概是八点五十左右。开班前一天就是来规定新的规矩的。彭老师说:“我们准...
    summer丶忘记阅读 363评论 2 1