這篇文章主要介紹了JavaScript實現求最大公共子字串的方法,涉及javascript針對字符串的遍歷、匹配、運算等相關操作技巧,需要的朋友可以參考下
本文實例講述了JavaScript實作求最大公共子字串的方法。分享給大家供大家參考，具體如下：
求最大公共子字串，常見的做法是使用矩陣。假設有字串：abcdefg和字串abcd，則可構成如下表所示矩陣。
可以，需要改變一下策略，如果該項匹配，則該項的值為再設為1，而是其對角線a[i-1, j-1](i > 1 && j > 1)的值1，這樣便可以只使用一個一維數組。將兩個字串的每一項都進行比較，若符合則該項為1，不符合則為0。然後求出對角線最長為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>登入後複製
上面是我整理給大家的，希望今後會對大家有幫助。
相關文章：
在vue.js中使用Nginx來解決跨域
在vue.js中使用Nginx來解決跨域
在vue webpack中如何實作非同步元件載入？
以上是在JavaScript中如何實作求最大公共子串的詳細內容。更多資訊請關注PHP中文網其他相關文章！
