c++ - 使用后缀数组和 LCP(-LR) 实现字符串模式匹配

Question

在过去的几周里，我试图找出如何有效地在另一个字符串中找到一个字符串模式。

我发现很长一段时间以来，最有效的方法一直是使用后缀树。然而，由于这种数据结构在空间上非常昂贵，我进一步研究了后缀数组的使用(它使用的空间要少得多)。不同的论文，如“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

添加了引用论文的链接

Answer 1

对你有帮助的术语: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]);
}