使用后缀数组寻找最长公共子字符串javaScript版

后缀数组很久很久以前就出现了，具体的概念读者自行搜索，小菜仅略知一二，不便讨论。

本文通过寻找两个字符串的最长公共子字符串，演示了后缀数组的经典应用。

首先需要说明，小菜实现的这个后缀数组算法，并非标准，只是借鉴了其中的思想。

小菜实现的算法，有两个版本，第一个是空间换时间，第二个是时间换空间。

空间换时间版本

  1 /*  2   利用后缀数组获取两个字符串最长公共子字符串  3   空间换时间版本  4   @params  5     s1 String，要分析的字符串  6     s2 String，要分析的字符串  7     norepeat Boolean，是否对结果进行去重，默认true  8 */  9 function commonSubString(s1, s2, norepeat){ 10   var norepeat = norepeat == undefined ? true : norepeat, 11       array = suffixArray(s1, 1).concat(suffixArray(s2, 2)), 12       maxLength = 0, 13       maxStrings = [], 14       tempLength = 0, 15       i = 0, 16       length = 0, 17       result = {}; 18    19   //排序，根据字符串排序，直接比较即可 20   array.sort(function(s1, s2){ 21     return (s1.s == s2.s) ? 0 : (s1.s > s2.s) ? 1 : -1; 22   }); 23    24   //寻找最长公共子字符串 25   for(i = 0, length = array.length - 1; i < length; i++){ 26     tempLength = commonLength(array[i].s, array[i+1].s); 27     if(array[i].g != array[i+1].g){ 28       if(maxLength == tempLength){ 29         maxStrings.push(array[i]); 30       } 31       if(maxLength < tempLength){ 32         maxLength = tempLength; 33         maxStrings = []; 34         maxStrings.push(array[i]); 35       } 36     } 37   } 38    39   //构造结果 40   result.length = maxLength; 41   result.contents = []; 42   for(i in maxStrings){ 43     result.contents.push(maxStrings[i].s.substring(0, maxLength)); 44   } 45    46   //去重 47   if(norepeat){ 48     result.contents  = norepeatArray(result.contents); 49   } 50    51   return result; 52    53   /* 54     获取字符串的后缀数组 55   */ 56   function suffixArray(s, g){ 57     var array = [], 58         i = 0, 59         length = s.length; 60     for(i = 0; i < length; i++){ 61       array.push({ 62         s: s.substring(i), 63         g: g   //加分组是为了保证最长公共子字符串分别来自两个字符串 64       }); 65     } 66      67     return array; 68   } 69   /* 70     获取最大匹配长度 71   */ 72   function commonLength(s1, s2){ 73     var slength = s1.length > s2.length ? s2.length : s1.length, 74         i = 0; 75      76     //循环次数=较短的字符串长度 77     for(i = 0; i < slength; i++){ 78       //逐位比较 79       if(s1.charAt(i) != s2.charAt(i)){ 80         break; 81       } 82     } 83      84     return i; 85   } 86    87   /* 88     字符串数组去重，不会影响原数组，返回一个新数组 89   */ 90   function norepeatArray(array){ 91     var _array = array.slice(0), 92         map = {}, 93         i = 0, 94         key = ""; 95      96     //将内容作为散列的key 97     for(i in _array){ 98       map[_array[i]] = 1; 99     }100     101     //提取散列key，重新填充到数组102     _array.splice(0, _array.length);103     for(key in map){104       _array.push(key);105     }106     107     return _array;108   }109 }

时间换空间版本

  1 /*  2   利用后缀数组获取两个字符串最长公共子字符串  3   时间换空间版本  4   @params  5     s1 String，要分析的字符串  6     s2 String，要分析的字符串  7     norepeat Boolean，是否对结果进行去重，默认true  8 */  9 function commonSubStringPRo(s1, s2, norepeat){ 10   var norepeat = norepeat == undefined ? true : norepeat, 11       array = suffixArray(s1, 1).concat(suffixArray(s2, 2)), 12       maxLength = 0, 13       maxStrings = [], 14       tempLength = 0, 15       i = 0, 16       length = 0, 17       result = {}; 18    19   //排序，根据实际内容排序，不能根据指针排序 20   array.sort(function(s1, s2){ 21     var ts1 = s1.str.substring(s1.index), 22         ts2 = s2.str.substring(s2.index); 23     return (ts1 == ts2) ? 0 : (ts1 > ts2) ? 1 : -1; 24   }); 25    26   //寻找最长公共子字符串 27   for(i = 0, length = array.length - 1; i < length; i++){ 28     tempLength = commonLength(array[i], array[i+1]); 29     if(array[i].group != array[i+1].group){ 30       if(maxLength == tempLength){ 31         maxStrings.push(array[i]); 32       } 33       if(maxLength < tempLength){ 34         maxLength = tempLength; 35         maxStrings = []; 36         maxStrings.push(array[i]); 37       } 38     } 39   } 40    41   //构造结果 42   result.length = maxLength; 43   result.contents = []; 44   for(i in maxStrings){ 45     result.contents.push(maxStrings[i].str.substr(maxStrings[i].index, maxLength)); 46   } 47    48   //去重 49   if(norepeat){ 50     result.contents  = norepeatArray(result.contents); 51   } 52    53   return result; 54    55   /* 56     获取字符串的后缀数组 57     只存指针，不存实际内容 58   */ 59   function suffixArray(s, g){ 60     var array = [], 61         i = 0, 62         length = 0; 63     for(i = 0, length = s.length; i < length; i++){ 64       array.push({ 65         index: i, 66         str: s,    //这里仅仅存放的是字符串指针，不会创建多个副本 67         group: g   //加分组是为了保证最长公共子字符串分别来自两个字符串 68       }); 69     } 70      71     return array; 72   } 73   /* 74     获取最大匹配长度 75   */ 76   function commonLength(s1, s2){ 77     var slength = 0, 78         i = 0; 79      80     //循环次数=较短的字符串长度 81     slength = (s1.str.length - s1.index) > (s2.str.length - s2.index) ? (s2.str.length - s2.index) : (s1.str.length - s1.index); 82     for(i = 0; i < slength; i++){ 83       //逐位比较 84       if(s1.str.substr(i + s1.index, 1) != s2.str.substr(i  + s2.index, 1)){ 85         break; 86       } 87     } 88      89     return i; 90   } 91    92   /* 93     字符串数组去重，不会影响原数组，返回一个新数组 94   */ 95   function norepeatArray(array){ 96     var _array = array.slice(0), 97         map = {}, 98         i = 0, 99         key = "";100     101     //将内容作为散列的key102     for(i in _array){103       map[_array[i]] = 1;104     }105     106     //提取散列key，重新填充到数组107     _array.splice(0, _array.length);108     for(key in map){109       _array.push(key);110     }111     112     return _array;113   }114 }

为啥会有两个版本呢？小菜原本只写了空间换时间版本，这个版本实现复杂度低，但是有一个明显的弊端，它占用了太多无谓的内存，分析数据量不大的时候，可以完美胜任，一旦数据量达到一定程度，它表现出来的不仅仅是执行时间变长，而是根本无法运行，除非有足够大的内存。

基于以上思考，小菜发现在生成后缀数组的时候，根本没必要保存实际字符串，只需记录位置信息即可，这样一来，内存中的大量字符串，均变成一个个整型数值，在做比较的时候，我们甚至不需要还原字符串，直接用位置去截取单个字符即可，最终内存极大节省，这就是时间换空间版本。

通过时间换空间，带来的不仅仅是节省内存，而是一种质的变化，从不可能变成可能，现在，无论有多大的数据量，只需很小一部分内存，即可支持程序运转，就算运行时间再长，它也是可行的，不会直接崩溃。当然，现在的CPU运行速度已经很快了。

希望对读者有所启发，至于具体代码，就不多说了，注释很详细。