最大公共子串算法
???? 有两种思想，就像珠宝商放在天鹅绒上的宝石一样熠熠生辉。一个是微积分，另一个就是算法。微积分以及在微积分基础上建立起的数学分析体系造就了现代科学，而算法造就了现代世界。
????????????????????????????????????????????????????????????????????????????????????????????????????????? ——David Berlinski
最大公共子串问题JavaScript版求最大公共子串，常见的做法是使用矩阵。假设有字符串：abcdefg和字符串abcd，则可构成如下矩阵。
view source print?
1????a??? b??? c??? d??? e??? f??? g 2a?? 1??? 0??? 0??? 0??? 0??? 0??? 0 3b?? 0??? 1??? 0??? 0??? 0??? 0??? 0 4c?? 0??? 0??? 1??? 0??? 0??? 0??? 0 5d?? 0??? 0??? 0??? 1??? 0??? 0??? 0对两个字符串的每一项都进行比较，若匹配则该项为1，不匹配则为0。然后求出对角线最长为1的那一段序列，即为最大公共子串。看上面的分开，似乎得使用二维数组了，在两个字符串都较大的情况下不是很划算，是否可以进一步优化？
可以，需要改变一下策略，如果该项匹配，则该项的值为再设为1，而是其对角线a[i-1, j-1](i > 1 && j > 1)的值+1，这样便可以只使用一个一维数组。
以一个字符串作为“行”，另一个作为“列”，比较两个字符串各项的值，用另外一个变量记录数组的最大值和字符串的起始位置。代码如下：
view source print?01function LCS(str1, str2) { 02??03????if (str1 === "" || str2 === "") { 04????????return ""; 05????} 06??07????var len1 = str1.length; 08????var len2 = str2.length; 09??????10????var a = new Array(len1); 11????var maxLen = 0; 12????var maxPos = 0; 13??????14????for (var i = 0; i < len1; i++) { //行 15????????for (var j = len2 - 1; j >= 0; j--) {//列? 16????????????if (str1.charAt(j) == str2.charAt(i)) { 17????????????????if (i === 0 || j === 0) { 18????????????????????a[j] = 1; 19????????????????} else { 20????????????????????a[j] = a[j - 1] + 1; 21????????????????} 22????????????} else { 23????????????????a[j] = 0; 24????????????} 25??26????????????if (a[j] > maxLen) { 27????????????????maxLen = a[j]; 28????????????????maxPos = j; 29????????????} 30????????} 31????} 32??33????return str1.substr(maxPos - maxLen + 1, maxLen); 34}但代码其实并不是最优的，为什么？因为上面的写法必须等待两层循环都完成。有没有相对更快一些的方法呢？
设有字符串a、b，其长度分别为len1、len2，其公共字子串一定是 <= Math.min(len1, len2)，而且子串必定连续，且一定是a、b的子串。
view source print?01function findMaxSubStr(s1,s2){? 02????var str= "", 03????????L1=s1.length, 04????????L2=s2.length;? 05??????06????if (L1>L2){? 07????????var s3=s1; 08????????s1=s2; 09????????s2=s3; 10????????s3 = null; 11????????L1=s2.length; 12????????L2 = s1.length; 13????} 14??????15??????16????for (var i=L1; i > 0; i--) { 17????????for (var j= 0; j <= L2 - i && j < L1; j++){? 18????????????str = s1.substr(j, i); 19????????????if (s2.indexOf(str) >= 0) { 20????????????????return str;? 21????????????} 22????????}? 23????} 24??????25????return "";? 26}先比较s1、s2的长度，然后取较短的字符串作为。substr(idex, len)，所以拿较短的串取其子串，然后判断它是否在较长的字符串中存在，如果存中则直接返回，否则再取下一位。
完整示例：
view source print?001<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 002<html xmlns="http://www.w3.org/1999/xhtml"> 003?<head> 004??<title>www.nowamagic.net</title> 005??<style type='text/css'> 006????body {background-color:#fff;} 007??</style> 008?</head> 009??010?<body> 011<script type='text/javascript'> 012function LCS(str1, str2) { 013??014????if (str1 === "" || str2 === "") { 015????????return ""; 016????} 017??018????var len1 = str1.length; 019????var len2 = str2.length; 020??????021????var a = new Array(len1); 022????var maxLen = 0; 023????var maxPos = 0; 024??????025????for (var i = 0; i < len1; i++) { //行 026????????for (var j = len2 - 1; j >= 0; j--) {//列? 027????????????if (str1.charAt(j) == str2.charAt(i)) { 028????????????????if (i === 0 || j === 0) { 029????????????????????a[j] = 1; 030????????????????} else { 031????????????????????a[j] = a[j - 1] + 1; 032????????????????} 033????????????} else { 034????????????????a[j] = 0; 035????????????} 036??037????????????if (a[j] > maxLen) { 038????????????????maxLen = a[j]; 039????????????????maxPos = j; 040????????????} 041????????} 042????} 043??044????return str1.substr(maxPos - maxLen + 1, maxLen); 045} 046??047??048function findMaxSubStr(s1,s2){? 049????var str= "", 050????L1=s1.length, 051????L2=s2.length;? 052??????053????if (L1>L2) {? 054????var s3=s1; 055????s1=s2; 056????s2=s3; 057????s3 = null; 058????L1=s2.length; 059????L2 = s1.length; 060????} 061??????062??????063????for (var i=L1; i > 0; i--) { 064????for (var j= 0; j <= L2 - i && j < L1; j++){? 065????????????str = s1.substr(j, i); 066????????????if (s2.indexOf(str) >= 0) { 067????????return str;? 068????????} 069???????}? 070????} 071??????072????return "";? 073}? 074??075??076????!(function() { 077????var tmpArr = []; 078????for (var i = 97; i < 97 + 26; i++) { 079????????tmpArr.push(String.fromCharCode(i)); 080????} 081??????082????var s2 = tmpArr.join(""); 083??084????tmpArr.sort(function() {return Math.random() > 0.7;}); 085????var s1 = new Array(600).join(tmpArr.join("")); 086??????087??????088????var date = getNow(); 089????alert(? "消耗时间：" + (getNow() - date) + "秒? " + LCS(s1, s2)); 090??091????date = getNow(); 092????alert(? "消耗时间：" + (getNow() - date) + "秒? " + findMaxSubStr(s1, s2) ); 093???})(); 094??095function getNow() { 096????return new Date().getTime(); 097} 098</script> 099?</body> 100</html>正文转载于http://www.nowamagic.net/algorithm/algorithm_LargestCommonSubstring.php
1 楼 暴风雪 2012-03-18 膜拜效率是O(n^2)的算法……为什么不用后缀树/后缀数组优化到O(logn)呢？