JavaScript求最大公共子串的两种算法实现
本文详解JavaScript中求最大公共子串的两种实现方式。首先介绍基于二维矩阵及一维数组优化的动态规划方法，通过状态转移方程减少空间复杂度；其次提供基于子串截取与indexOf判断的暴力枚举法，通过缩短基准字符串长度提升效率。文章包含完整代码示例与性能对比分析，适用于字符串处理场景。
本文通过具体实例介绍在JavaScript环境中计算两个字符串最大公共子串的实现方案，供开发者参考与借鉴。
基于矩阵的动态规划解法
计算最大公共子串的经典思路通常借助矩阵结构。假设存在字符串“abcdefg”与“abcd”，可构建如下所示的对比矩阵。
| a | b | c | d | e | f | g | |
| a | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| b | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| c | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| d | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
遍历两个字符串的字符进行逐项比对，若字符匹配则对应位置标记为1，否则标记为0。随后寻找对角线上连续为1的最长序列，该序列即代表最大公共子串。观察上述矩阵可知，传统方法需使用二维数组，当字符串长度较大时，这种空间占用方式效率较低，因此存在优化空间。
可以通过调整策略来优化空间复杂度。若当前字符匹配，不再单纯标记为1，而是将其值设为对角线位置a[i-1, j-1]（需满足i > 1且j > 1）的值加1。借助这一状态转移逻辑，仅需维护一个一维数组即可完成计算。
实现时，可将一个字符串视为“行”，另一个视为“列”，遍历比对字符。同时使用额外变量记录数组中的最大值及其对应的字符串起始索引。具体实现代码如下：
function LCS(str1, str2) {
if (str1 === "" || str2 === "") {
return "";
}
var len1 = str1.length;
var len2 = str2.length;
var a = new Array(len1);
var maxLen = 0;
var maxPos = 0;
for (var i = 0; i < len1; i++) { //行
for (var j = len2 - 1; j >= 0; j--) {//列
if (str1.charAt(j) == str2.charAt(i)) {
if (i === 0 || j === 0) {
a[j] = 1;
} else {
a[j] = a[j - 1] + 1;
}
} else {
a[j] = 0;
}
if (a[j] > maxLen) {
maxLen = a[j];
maxPos = j;
}
}
}
return str1.substr(maxPos - maxLen + 1, maxLen);
}
基于子串截取的暴力枚举优化
上述代码并非性能最优解，原因在于其必须等待双层循环完全执行完毕才能得出结果。是否存在执行效率更高的替代方案？
假设字符串a与b的长度分别为len1和len2，它们的最大公共子串长度必然小于等于Math.min(len1, len2)。此外，公共子串必须是连续的，且同时存在于a和b中。
function findMaxSubStr(s1,s2){
var str= "",
L1=s1.length,
L2=s2.length;
if (L1>L2){
var s3=s1;
s1=s2;
s2=s3;
s3 = null;
L1=s2.length;
L2 = s1.length;
}
for (var i=L1; i > 0; i--) {
for (var j= 0; j <= L2 - i && j < L1; j++){
str = s1.substr(j, i);
if (s2.indexOf(str) >= 0) {
return str;
}
}
}
return "";
}
首先比较s1与s2的长度，选取较短的字符串作为substr(idex, len)，即从较短字符串中提取子串，然后判断该子串是否存在于较长的字符串中。若存在则直接返回结果；否则继续提取下一个子串进行判断。
完整的测试示例如下：
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>www.jb51.net</title>
<style type='text/css'>
body {background-color:#fff;}
</style>
</head>
<body>
<script type='text/javascript'>
function LCS(str1, str2) {
if (str1 === "" || str2 === "") {
return "";
}
var len1 = str1.length;
var len2 = str2.length;
var a = new Array(len1);
var maxLen = 0;
var maxPos = 0;
for (var i = 0; i < len1; i++) { //行
for (var j = len2 - 1; j >= 0; j--) {//列
if (str1.charAt(j) == str2.charAt(i)) {
if (i === 0 || j === 0) {
a[j] = 1;
} else {
a[j] = a[j - 1] + 1;
}
} else {
a[j] = 0;
}
if (a[j] > maxLen) {
maxLen = a[j];
maxPos = j;
}
}
}
return str1.substr(maxPos - maxLen + 1, maxLen);
}
function findMaxSubStr(s1,s2){
var str= "",
L1=s1.length,
L2=s2.length;
if (L1>L2) {
var s3=s1;
s1=s2;
s2=s3;
s3 = null;
L1=s2.length;
L2 = s1.length;
}
for (var i=L1; i > 0; i--) {
for (var j= 0; j <= L2 - i && j < L1; j++){
str = s1.substr(j, i);
if (s2.indexOf(str) >= 0) {
return str;
}
}
}
return "";
}
!(function() {
var tmpArr = [];
for (var i = 97; i < 97 + 26; i++) {
tmpArr.push(String.fromCharCode(i));
}
var s2 = tmpArr.join("");
tmpArr.sort(function() {return Math.random() > 0.7;});
var s1 = new Array(600).join(tmpArr.join(""));
var date = getNow();
alert( "消耗时间：" + (getNow() - date) + "秒 " + LCS(s1, s2));
date = getNow();
alert( "消耗时间：" + (getNow() - date) + "秒 " + findMaxSubStr(s1, s2) );
})();
function getNow() {
return new Date().getTime();
}
</script>
</body>
</html>
如需了解更多JavaScript相关知识，可参考本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》。
希望本文所述的算法实现能对读者的JavaScript编程工作提供有益帮助。
D3.js 比例尺与坐标轴的配置详解
2026-11-05 16:54:46
JavaScript怎么遍历对象的Symbol键和不可枚举属性
2026-11-05 13:13:39
封装一个健壮的JS字符串判空工具函数
2026-11-05 12:16:14
JavaScript合并数组的三种常用方法：concat、扩展运算符与push
2026-11-05 11:22:29
JavaScript立即执行函数(IIFE)是什么及基本语法
2026-11-05 10:51:19