问题标签 [knuth-morris-pratt]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
java - Java中的字符串比较,我应该使用哪种算法?
我需要将用户将搜索的产品名称与可用产品进行比较。我有存储在 MySQL 数据库中的产品名称。我正在收集所有名称,并在我的 java 服务启动时将其带到应用程序级别(java)。
现在我的字符串比较场景是这样的:
谁能建议在Java中哪种算法适合这个?还有一件事,将所有产品名称从 MySQL 带到应用程序级别(java)是正确的方法吗?或者我也可以在 MySQL 级别做吗?(PS:我不想在 MySQL 端使用 like 查询,因为它会很慢)
algorithm - Knuth-Morris-Pratt 算法极端案例
在 Knuth-Morris-Pratt 算法中,当“子串”词是相同字母的序列时,例如。“AAAAAAA...”,故障表是这样的:“-1, 0, 1, 2, 3, 4, 5,...”。
这意味着如果测试类似于“AAAAAAAB”,当我们到达“B”时,我们将返回 X 个字符并再次开始尝试匹配,尽管我们知道我们应该在 B 之后开始。
我错过了什么吗?
编辑(使示例具体):
假设测试是:AAAAAAAABAAAAAAAAA,即 (8 As, B, 9 As),而寻找的词是 AAAAAAAAA,即 (9 As)。
失败表将为:-1、0、1、2、3、4、5、6、7。
在某些时候它将是 m = 0,i = 8。这将失败,所以 m 将变为 m = m + i - T[8] = 0 + 8 - 7 => m = 1,而 i 将是 T[8 ] = 7。
这将再次失败,所以现在我们将有 m = 2、i = 6,然后是 m = 3、i = 7,等等。
strstr - strstr() vs 克努斯·莫里斯·普拉特
有人可以帮我理解哪个更有效 strstr() 或 KMP,因为最近我在 SPOJ 上做一个问题,发现 strstr() 以某种方式比 KMP 更快。有人请解释这背后的奥秘。 .
algorithm - Knuth Morris Pratt 算法比较
我在备考时遇到这个问题,请大家帮忙
对于模式 P 和文本 T 的任意对齐,假设在 KMP 算法执行过程中 P[i+1] 和 T[k] 发生不匹配 KMP 执行过程中,T[k] 总共比较了多少次算法(SPi 未优化)
我遇到的可能解决方案是
- i-SPi
- SPI+1
- 你
- n-SPi
但在某些情况下它们都失败了,
string - Is it possible to use the KMP algorithm to find a longest substring?
Suppose I have a pattern P and some text T, and I want to find the largest prefix of P that matches a substring of T. Is it possible to modify the KMP algorithm to do such an operation? (If I remember correctly, the KMP algorithm does partial matches, but I am interested in the longest possible match).
string - KMP 修改 - 在字符串中搜索简单的模板匹配
我想在字符串 S 中找到与正则表达式 R 匹配的所有子字符串。正则表达式只能包含“。” 和符号(其中“.”表示任何符号)。我正在尝试使用 KMP 来解决这个问题:
1) 构建字符串 T = R + '#' + S ('#' 在这里是分隔符)
2) 计算前缀函数。对于 T
3) 对于 pi(T 的前缀函数)检查 '#' 之后的位置,其中 pi[i] == len(S)。在这些位置寻找子串结束。
但是前缀功能。不能在带有 '.' 的字符串上正常工作 我的前缀函数代码:
它在测试 S="abab", T="a." 时失败。
我知道可以使用 KMP 来解决这个问题,你能告诉我怎么做吗?
algorithm - Knuth-Morris-Pratt 失败表
我正在准备考试,并且正在研究 Knuth-Morris-Pratt 算法。考试内容是 Fail 表和 DFA 构造。我了解 DFA 构造,但我并不真正了解如何制作失败表。
如果我有一个模式“abababc”的例子,我该如何构建一个失败表?解决方案是:
失败表:
0 1 2 3 4 5 6 7
0 0 0 1 2 3 4 0
但我怎么得到呢?没有代码只是解释如何获得它是必要的。
string - 何时使用 Rabin-Karp 或 KMP 算法?
我使用以下字母生成了一个字符串。
{A,C,G,T}
. 我的字符串包含超过 10000 个字符。我正在其中搜索以下模式。
- ATGGA
- TGGAC
- CCGT
我已要求使用具有O(m+n)
运行时间的字符串匹配算法。
两者KMP and Rabin-Karp algorithms
都有这个运行时间。在这种情况下,最合适的算法(在 Rabin-Carp 和 KMP 之间)是什么?
scala - 尾递归 Knuth-Morris-Pratt 算法
我在 Scala 中创建了Knuth-Morris-Pratt 算法的简单实现。现在我想变得花哨并以尾递归的方式做同样的事情。我的直觉告诉我这不应该太难(表格和搜索部分),但同样的感觉也告诉我,这一定是有人已经完成了,可能比我更聪明。因此问题。你知道 Knuth-Morris-Pratt 算法的任何尾递归实现吗?
java - Knuth Morris Pratt 应用程序没有错误但无法正常工作
这是我的申请
“Textform”,从搜索框中获取值。
“listKamus”,从数组中取值。然后“玩家名称”,将其值更改为字符串。
"KMP.knutMorris(textform, playerName)", 发送 textform, playerName 值到 knutMorris 类
主要课程
KMP 级
我希望人们在搜索框中键入时显示正确的数组列表。
我认为错误之一在这里
主要课程
或者在这里
KMP 级
谁能告诉我如何解决这个问题?