使用后缀数组和LCP（-LR）实现字符串模式匹配
在过去的几周里，我试图弄清楚如何在另一个字符串中有效地找到字符串模式。
我发现很长一段时间，最有效的方法是使用后缀树。 但是，由于这种数据结构在空间上非常昂贵，我进一步研究了后缀数组的使用（使用的空间要少得多）。 不同的论文，如“后缀数组：一种新的在线字符串搜索方法”（Manber＆Myers，1993）指出，搜索子字符串可以在O（P + log（N））中实现（其中P是通过使用二进制搜索和后缀数组以及LCP数组，模式的长度和N是字符串的长度。
我特别研究了后一篇论文来理解搜索算法。 这个答案在帮助我理解算法方面做得很好（顺便把它变成了LCP维基百科页面 ）。
但我仍在寻找实现此算法的方法。 特别是所提到的LCP-LRarrays的构造看起来非常复杂。
参考文献：
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数组，并找到了实现它们的方法。 但是，“普通”LCParrays不适合有效的模式匹配（如参考文献中所述）。 因此，我对实现LCP-LRarrays感兴趣，这似乎比实现LCParrays复杂得多
更新2
添加了参考文件的链接
可以帮助你的终端： enchanced suffix array ，用于描述带有各种其他数组的后缀数组，以替换后缀树（ lcp ，child）。
这些可以是一些例子：
https://code.google.com/p/esaxx/ ESAXX
http://bibiserv.techfak.uni-bielefeld.de/mkesa/ MKESA
esaxx似乎正在做你想要的，另外，它有例子enumSubstring.cpp如何使用它。
如果你看一下参考文献 ，它会提到一个有用的属性(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 ++中一个相当简单的实现，尽管build()过程在O(N lg^2 N)时间内构建后缀数组。 lcp_compute()过程具有线性复杂性。 我在很多编程竞赛中都使用过这段代码，它从来没有让我失望:)
#include #include #include using namespace std; const int MAX = 200005; char str[MAX]; int N, h, sa[MAX], pos[MAX], tmp[MAX], lcp[MAX]; bool compare(int i, int j) { if(pos[i] != pos[j]) return pos[i] < pos[j]; // compare by the first h chars i += h, j += h; // if prefvious comparing failed, use 2*h chars return (i < N && j < N) ? pos[i] < pos[j] : i > j; // return results } void build() { N = strlen(str); for(int i=0; i
注意：如果您希望build()过程的复杂性变为O(N lg N) ，则可以使用基数排序替换STL排序，但这会使代码复杂化。
编辑：对不起，我误解了你的问题。 虽然我没有使用后缀数组实现字符串匹配，但我想我可以用一种简单的非标准但相当有效的字符串匹配算法来描述你。 您将获得两个字符串， text和pattern 。 给定这些字符串，你创建一个新的字符串，让我们称之为concat ，这是两个给定字符串的串联（首先是text ，然后是pattern ）。 您在concat上运行后缀数组构造算法，并构建正常的lcp数组。 然后，在刚刚构建的后缀数组中搜索长度为pattern.size()的后缀。 让我们在后缀数组pos调用它的位置。 然后你需要两个指针lo和hi 。 在开始lo = hi = pos 。 你减少lo而lcp(lo, pos) = pattern.size()你增加hi而lcp(hi, pos) = pattern.size() 。 然后在[lo, hi]范围内搜索长度至少为2*pattern.size()的后缀。 如果你找到它，你找到了匹配。 否则，不存在匹配。
编辑[2]：我有一个实施，我会尽快回来......
编辑[3]：
这里是：
// It works assuming you have builded the concatenated string and // computed the suffix and the lcp arrays // text.length() ---> tlen // pattern.length() ---> plen // concatenated string: str bool match(int tlen, int plen) { int total = tlen + plen; int pos = -1; for(int i=0; i= 0 && lcp[lo-1] >= plen) lo--; while(hi+1 < N && lcp[hi] >= plen) hi++; for(int i=lo; i<=hi; ++i) if(total-sa[i] >= 2*plen) return true; return false; }
这是一个很好的post，包括一些代码，可以帮助您更好地理解LCP数组和比较实现。
我理解你的愿望是代码，而不是实现自己的代码。 虽然是用Java编写的，但它是由Sedgewick和Wayne在他们的算法书籍网站上 实现的带有LCP的Suffix数组 。 它应该节省您一些时间，并且不应该非常难以移植到C / C ++。
伪造的LCP数组构造适用于那些可能需要更多有关算法信息的人。
我认为@ Erti-Chris Eelmaa的算法是错误的。
L ... 'M ... M ... M' ... R |-----|-----|
左子范围和右子范围都应该包含M.因此我们不能为LCP-LR数组做正常的分段树分区。 代码应该看起来像
def lcp_from_i_j(i, j): # means [i, j] not [i, j) if (ji<1) return lcp_2_elem(i, j) return lcp_merge(lcp_from_i_j(i, (i+j)/2), lcp_from_i_j((i+j)/2, j)
左侧和右侧子范围重叠。 段树支持范围最小查询。 但是，[a，b]之间的范围min不等于[a，b]之间的lcp。 LCParrays是连续的，简单的范围min不起作用！