我使用标准二进制搜索来快速返回排序列表中的单个对象(相对于可排序属性).
现在我需要修改搜索,以便返回所有匹配列表条目.我该怎么做才能做到最好？
在过去的几周里,我试图弄清楚如何在另一个字符串中有效地找到字符串模式.
我发现很长一段时间,最有效的方法是使用后缀树.但是,由于这种数据结构在空间上非常昂贵,我进一步研究了后缀数组的使用(使用的空间要少得多).不同的论文,如"后缀数组:一种新的在线字符串搜索方法"(Manber&Myers,1993)指出,搜索子字符串可以在O(P + log(N))中实现(其中P是通过使用二进制搜索和后缀数组以及LCP数组,模式的长度和N是字符串的长度.
我特别研究了后一篇论文来理解搜索算法.这个答案在帮助我理解算法方面做得非常出色(并顺便将其纳入LCP维基百科页面).
但我仍在寻找实现此算法的方法.特别是所提到的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
添加了参考文件的链接