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

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

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

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

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

空间换时间版本

/*
利用后缀数组获取两个字符串最长公共子字符串
空间换时间版本
@params
s1 String，要分析的字符串
s2 String，要分析的字符串
norepeat Boolean，是否对结果进行去重，默认true
*/
function commonSubString(s1, s2, norepeat){
var norepeat = norepeat == undefined ? true : norepeat,
array = suffixArray(s1, 1).concat(suffixArray(s2, 2)),
maxLength = 0,
maxStrings = [],
tempLength = 0,
i = 0,
length = 0,
result = {}; //排序，根据字符串排序，直接比较即可
array.sort(function(s1, s2){
return (s1.s == s2.s) ? 0 : (s1.s > s2.s) ? 1 : -1;
}); //寻找最长公共子字符串
for(i = 0, length = array.length - 1; i < length; i++){
tempLength = commonLength(array[i].s, array[i+1].s);
if(array[i].g != array[i+1].g){
if(maxLength == tempLength){
maxStrings.push(array[i]);
}
if(maxLength < tempLength){
maxLength = tempLength;
maxStrings = [];
maxStrings.push(array[i]);
}
}
} //构造结果
result.length = maxLength;
result.contents = [];
for(i in maxStrings){
result.contents.push(maxStrings[i].s.substring(0, maxLength));
} //去重
if(norepeat){
result.contents = norepeatArray(result.contents);
} return result; /*
获取字符串的后缀数组
*/
function suffixArray(s, g){
var array = [],
i = 0,
length = s.length;
for(i = 0; i < length; i++){
array.push({
s: s.substring(i),
g: g //加分组是为了保证最长公共子字符串分别来自两个字符串
});
} return array;
}
/*
获取最大匹配长度
*/
function commonLength(s1, s2){
var slength = s1.length > s2.length ? s2.length : s1.length,
i = 0; //循环次数=较短的字符串长度
for(i = 0; i < slength; i++){
//逐位比较
if(s1.charAt(i) != s2.charAt(i)){
break;
}
} return i;
} /*
字符串数组去重，不会影响原数组，返回一个新数组
*/
function norepeatArray(array){
var _array = array.slice(0),
map = {},
i = 0,
key = ""; //将内容作为散列的key
for(i in _array){
map[_array[i]] = 1;
} //提取散列key，重新填充到数组
_array.splice(0, _array.length);
for(key in map){
_array.push(key);
} return _array;
}
}

时间换空间版本

/*
利用后缀数组获取两个字符串最长公共子字符串
时间换空间版本
@params
s1 String，要分析的字符串
s2 String，要分析的字符串
norepeat Boolean，是否对结果进行去重，默认true
*/
function commonSubStringPro(s1, s2, norepeat){
var norepeat = norepeat == undefined ? true : norepeat,
array = suffixArray(s1, 1).concat(suffixArray(s2, 2)),
maxLength = 0,
maxStrings = [],
tempLength = 0,
i = 0,
length = 0,
result = {}; //排序，根据实际内容排序，不能根据指针排序
array.sort(function(s1, s2){
var ts1 = s1.str.substring(s1.index),
ts2 = s2.str.substring(s2.index);
return (ts1 == ts2) ? 0 : (ts1 > ts2) ? 1 : -1;
}); //寻找最长公共子字符串
for(i = 0, length = array.length - 1; i < length; i++){
tempLength = commonLength(array[i], array[i+1]);
if(array[i].group != array[i+1].group){
if(maxLength == tempLength){
maxStrings.push(array[i]);
}
if(maxLength < tempLength){
maxLength = tempLength;
maxStrings = [];
maxStrings.push(array[i]);
}
}
} //构造结果
result.length = maxLength;
result.contents = [];
for(i in maxStrings){
result.contents.push(maxStrings[i].str.substr(maxStrings[i].index, maxLength));
} //去重
if(norepeat){
result.contents = norepeatArray(result.contents);
} return result; /*
获取字符串的后缀数组
只存指针，不存实际内容
*/
function suffixArray(s, g){
var array = [],
i = 0,
length = 0;
for(i = 0, length = s.length; i < length; i++){
array.push({
index: i,
str: s, //这里仅仅存放的是字符串指针，不会创建多个副本
group: g //加分组是为了保证最长公共子字符串分别来自两个字符串
});
} return array;
}
/*
获取最大匹配长度
*/
function commonLength(s1, s2){
var slength = 0,
i = 0; //循环次数=较短的字符串长度
slength = (s1.str.length - s1.index) > (s2.str.length - s2.index) ? (s2.str.length - s2.index) : (s1.str.length - s1.index);
for(i = 0; i < slength; i++){
//逐位比较
if(s1.str.substr(i + s1.index, 1) != s2.str.substr(i + s2.index, 1)){
break;
}
} return i;
} /*
字符串数组去重，不会影响原数组，返回一个新数组
*/
function norepeatArray(array){
var _array = array.slice(0),
map = {},
i = 0,
key = ""; //将内容作为散列的key
for(i in _array){
map[_array[i]] = 1;
} //提取散列key，重新填充到数组
_array.splice(0, _array.length);
for(key in map){
_array.push(key);
} return _array;
}
}