在过去的几周里,我试图找出如何有效地在另一个字符串中找到一个字符串模式。
我发现很长一段时间以来,最有效的方法一直是使用后缀树。然而,由于这种数据结构在空间上非常昂贵,我进一步研究了后缀数组的使用(它使用的空间要少得多)。不同的论文,如“Suffix Arrays: A new method for on-line string searches”(Manber & Myers, 1993)指出,搜索子串可以在 O(P+log(N)) 中实现(其中 P 是模式的长度,N 是字符串的长度)通过使用二进制搜索和后缀数组以及 LCP 数组。
为了理解搜索算法,我专门研究了后面的论文。 This answer在帮助我理解算法方面做得很好(顺便说一句,它进入了 LCP Wikipedia Page )。
但是我还在寻找一种方法来实现这个算法。尤其是前面提到的LCP-LR阵列的构建显得非常复杂。
引用资料:
Manber & Myers,1993:Manber、Udi; Myers, Gene, SIAM Journal on Computing, 1993, Vol.22(5), pp.935-948, http://epubs.siam.org/doi/pdf/10.1137/0222058
更新 1
只是强调我感兴趣的内容:我了解 LCP 阵列并找到了实现它们的方法。但是,“普通”LCP 阵列不适用于高效模式匹配(如引用资料中所述)。因此,我对实现 LCP-LR 阵列很感兴趣,这似乎比仅实现 LCP 阵列复杂得多
更新 2
添加了引用论文的链接
最佳答案
对你有帮助的术语:enchanced suffix array
,用于描述后缀数组和其他各种数组,以取代后缀树(lcp,child)。
这些可以是一些例子:
https://code.google.com/p/esaxx/ ESAXX
http://bibiserv.techfak.uni-bielefeld.de/mkesa/ MKESA
esaxx 似乎正在做你想做的事,另外,它有示例 enumSubstring.cpp 如何使用它。
如果您查看引用的 paper ,它提到了一个有用的属性 (4.2)
。由于 SO 不支持数学,因此没有必要在此处复制它。
我已经完成了快速实现,它使用线段树:
// note that arrSize is O(n)
// int arrSize = 2 * 2 ^ (log(N) + 1) + 1; // start from 1
// LCP = new int[N];
// fill the LCP...
// LCP_LR = new int[arrSize];
// memset(LCP_LR, maxValueOfInteger, arrSize);
//
// init: buildLCP_LR(1, 1, N);
// LCP_LR[1] == [1..N]
// LCP_LR[2] == [1..N/2]
// LCP_LR[3] == [N/2+1 .. N]
// rangeI = LCP_LR[i]
// rangeILeft = LCP_LR[2 * i]
// rangeIRight = LCP_LR[2 * i + 1]
// ..etc
void buildLCP_LR(int index, int low, int high)
{
if(low == high)
{
LCP_LR[index] = LCP[low];
return;
}
int mid = (low + high) / 2;
buildLCP_LR(2*index, low, mid);
buildLCP_LR(2*index+1, mid + 1, high);
LCP_LR[index] = min(LCP_LR[2*index], LCP_LR[2*index + 1]);
}
关于c++ - 使用后缀数组和 LCP(-LR) 实现字符串模式匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27768429/