本文實例講述了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.49028c.com</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程序設計有所幫助。
新聞熱點
疑難解答
