后缀数组很久很久以前就出现了，具体的概念读者自行搜索，小菜仅略知一二，不便讨论。
本文通过寻找两个字符串的最长公共子字符串，演示了后缀数组的经典应用。
首先需要说明，小菜实现的这个后缀数组算法，并非标准，只是借鉴了其中的思想。
小菜实现的算法，有两个版本，第一个是空间换时间，第二个是时间换空间。
空间换时间版本
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 }View Code
时间换空间版本
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 }View Code
为啥会有两个版本呢？小菜原本只写了空间换时间版本，这个版本实现复杂度低，但是有一个明显的弊端，它占用了太多无谓的内存，分析数据量不大的时候，可以完美胜任，一旦数据量达到一定程度，它表现出来的不仅仅是执行时间变长，而是根本无法运行，除非有足够大的内存。
基于以上思考，小菜发现在生成后缀数组的时候，根本没必要保存实际字符串，只需记录位置信息即可，这样一来，内存中的大量字符串，均变成一个个整型数值，在做比较的时候，我们甚至不需要还原字符串，直接用位置去截取单个字符即可，最终内存极大节省，这就是时间换空间版本。
通过时间换空间，带来的不仅仅是节省内存，而是一种质的变化，从不可能变成可能，现在，无论有多大的数据量，只需很小一部分内存，即可支持程序运转，就算运行时间再长，它也是可行的，不会直接崩溃。当然，现在的CPU运行速度已经很快了。
希望对读者有所启发，至于具体代码，就不多说了，注释很详细。
原标题：使用后缀数组寻找最长公共子字符串JavaScript版
关键词：JavaScript
我知道了 