- android - RelativeLayout 背景可绘制重叠内容
- android - 如何链接 cpufeatures lib 以获取 native android 库?
- java - OnItemClickListener 不起作用,但 OnLongItemClickListener 在自定义 ListView 中起作用
- java - Android 文件转字符串
在过去的几周里,我试图找出如何有效地在另一个字符串中找到一个字符串模式。
我发现很长一段时间以来,最有效的方法一直是使用后缀树。然而,由于这种数据结构在空间上非常昂贵,我进一步研究了后缀数组的使用(它使用的空间要少得多)。不同的论文,如“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/
我对以下内容感到困惑quote来自维基百科: In other words, if a language was reasonable enough to allow an efficient one
我正在努力研究解析器理论,但我一直在不同的来源中找到相同的示例。语法大致如下(简化): E = T E = E + T T = 0..9 所以假设字符串 2 + 2 将被这样解析(“|”将堆栈与提醒分
PUSH{lr}的等效指令是什么?和 POP{lr}在 ARM Arch64 指令集中。 是 STR X30, [SP, #8]正确的 ?你能解释一下保持堆栈对齐的概念吗?我对 ARMv8 比较陌生,
是否有一个很好的在线资源,其中包含一些主要解析算法(LL(1)、LR(1)、LR(0)、LALR(1))的语法集合?我发现了许多属于这些家族的单独语法,但据我所知,没有什么好的资源可以让人编写大量示例
我使用IAR编译例程,但在ARM A7上运行错误;然后当我打开 IAR 生成的 .lst 文件时,我得到了以下问题。 它是一个ISR,首先push {r3, r4, r5, lr},但是POP {r0
我想知道 LR 属性解析器可以做什么以及它是如何实现的。 yacc 生成的解析器允许在属性源是使用 $0、$-1 等规范语法位于左侧的兄弟时继承属性。使用 S -> A B B 将能够从 A 继承一个
我想使用“merc_timer_handle_t”来记录loadrunner中的时间,但是当我创建场景时,LR给出错误消息:“第15行靠近“MasterT”的语法错误” . 我想知道如何使用“merc
我正在使用 ray RLlib 库在 5 排游戏中训练多智能体训练器。这是零和环境,所以我有代理人行为退化的问题(总是赢得第一个代理人,5 步获胜)。我有一个想法以这种方式改变代理人的学习率:首先训练
我是 Graphviz 的新手,尝试使用如下所示从左到右布局一些节点: digraph g { graph [ rankdir = "LR" ]; node [ fontsize = "16", f
LR(1) 解析器可以解析这种类型的语法吗? S -> SA | A A -> aSb | ab 我正在尝试编写一个实现此类解析器的 Java 程序,但我只能在没有左递归的语法上获得正确的结果。 最
从历史上看,LALR(1) 解析器比 LR(1) 解析器更受青睐,因为 LR(1) 解析器生成的大量状态需要资源。很难相信这仍然是当今计算环境中的一个问题。情况仍然如此,还是现代编译器现在使用规范的
我是编译主题的新手,刚刚开始自下而上解析的练习。 我一直坚持以下问题。 为以下文法建立一个LR(0)解析表: 1) E –> E + T 2) E –> T 3) T –> (E) 4) T –> i
我有一个我无法解决的 LR(1) 冲突语法;然而,语法应该是明确的。我将首先使用五个标记在简化语法上演示问题:(, ), {}, , 和 id。 EBNF 看起来像这样: args = (
假设 G(增强语法): E' - > E E - > E+T|T T - > T*F|F F - > (E)|id 因此,在 dfa 的创建级别之一中,我已经达到了这一点:(龙书中的 I6)
我经常看到以 lr 指针终止的 ARM 堆栈跟踪(阅读:Android NDK 堆栈跟踪),如下所示: #00 pc 001c6c20 /data/data/com.audia.dev
我使用的是 ARM Cortex-M4 处理器。据我了解,LR(链接寄存器)存储当前执行函数的返回地址。但是,内联和/或裸函数会影响它吗? 我正在努力实现简单的多任务处理。我想写一些代码来保存执行上下
我正在尝试为一种将用于生成其他文件的模板(配置)文件构建一个简单的 LR 解析器。我已经阅读和阅读了有关 LR 解析器的信息,但我似乎无法理解它!我知道有一个解析栈,一个状态栈和一个解析表。 toke
我在理解LR(1)-项目中的超前原理方面遇到困难。如何计算超前集? 例如,我有以下语法: S -> AB A -> aAb | b B -> d 然后,第一个状态将如下所示: S -> .AB , {
我正在学习“Engineering a Compiler, 2nd Edition”。我知道什么是LR(1)文法,但我在这本书中找不到运算符优先文法。 然后我从图书馆借了《编译器——原理、技术和工具》
我至少读过十几遍维基百科的解释,但我仍然对 LR(0) 解析器如何离开状态 0 感到困惑。 Wikipedia's example, with its explanation, says : The
我是一名优秀的程序员,十分优秀!