- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在尝试调整 Boyer-Moore c(++) Wikipedia implementation获取字符串中模式的所有匹配项。实际上,维基百科实现返回第一个匹配项。主要代码如下:
char* boyer_moore (uint8_t *string, uint32_t stringlen, uint8_t *pat, uint32_t patlen) {
int i;
int delta1[ALPHABET_LEN];
int *delta2 = malloc(patlen * sizeof(int));
make_delta1(delta1, pat, patlen);
make_delta2(delta2, pat, patlen);
i = patlen-1;
while (i < stringlen) {
int j = patlen-1;
while (j >= 0 && (string[i] == pat[j])) {
--i;
--j;
}
if (j < 0) {
free(delta2);
return (string + i+1);
}
i += max(delta1[string[i]], delta2[j]);
}
free(delta2);
return NULL;
}
我曾尝试修改 if (j < 0)
之后的区 block 将索引添加到数组/vector 并让外循环继续,但它似乎不起作用。在测试修改后的代码时,我仍然只得到一个匹配项。也许这个实现并不是为了返回所有匹配项而设计的,它需要进行一些快速更改才能做到这一点?我不太了解算法本身,所以我不确定如何进行这项工作。如果有人能指出正确的方向,我将不胜感激。
注意:函数 make_delta1 和 make_delta2 在源代码中较早定义(查看维基百科页面),而 max() 函数调用实际上也是在源代码中较早定义的宏。
最佳答案
Boyer-Moore 的算法利用了这样一个事实,即当在较长的字符串中搜索“HELLO WORLD”时,如果要在总的来说,有点像海战游戏:如果你在距离边界的四个单元格处找到公海,你就不需要测试剩下的四个单元格,以防那里藏着一个 5 单元格的航母;不可能。
例如,如果您在第 11 个位置找到一个“D”,它可能是 HELLO WORLD 的最后一个字母;但是如果你发现一个'Q','Q'不在HELLO WORLD 中的任何地方,这意味着搜索的字符串不能在前十一个字符中的任何地方,你可以完全避免搜索那里。另一方面,“L”可能意味着 HELLO WORLD 就在那里,从位置 11-3(HELLO WORLD 的第三个字母是 L)、11-4 或 11-10 开始。
搜索时,您使用两个增量数组跟踪这些可能性。
所以当你找到一个模式时,你应该这样做,
if (j < 0)
{
// Found a pattern from position i+1 to i+1+patlen
// Add vector or whatever is needed; check we don't overflow it.
if (index_size+1 >= index_counter)
{
index[index_counter] = 0;
return index_size;
}
index[index_counter++] = i+1;
// Reinitialize j to restart search
j = patlen-1;
// Reinitialize i to start at i+1+patlen
i += patlen +1; // (not completely sure of that +1)
// Do not free delta2
// free(delta2);
// Continue loop without altering i again
continue;
}
i += max(delta1[string[i]], delta2[j]);
}
free(delta2);
index[index_counter] = 0;
return index_counter;
如果您传递类似于 size_t *indexes
的内容,这应该返回一个以零结尾的索引列表。到函数。
然后该函数将返回 0(未找到)、index_size(太多匹配)或 1 和 index_size-1 之间的匹配数。
例如,这允许添加额外的匹配项,而不必重复整个搜索已找到的 (index_size-1) 个子字符串;你增加num_indexes
通过 new_num,realloc
indexes
数组,然后将偏移量 old_index_size-1
处的新数组传递给函数, new_num 作为新的大小,haystack 字符串从索引 old_index_size-1
处匹配的偏移量开始加上一个(不是,正如我在之前的修订版中所写,加上针串的长度;见评论)。
这种方法也会报告重叠匹配,例如在 banana 中搜索 ana 会找到 b*ana*na 和 ban*ana*.
更新
我测试了上面的内容,它似乎有效。我通过添加这两个包含来修改维基百科代码,以防止 gcc 提示
#include <stdio.h>
#include <string.h>
然后我修改了if (j < 0)
简单地输出它找到的内容
if (j < 0) {
printf("Found %s at offset %d: %s\n", pat, i+1, string+i+1);
//free(delta2);
// return (string + i+1);
i += patlen + 1;
j = patlen - 1;
continue;
}
最后我用这个测试了
int main(void)
{
char *s = "This is a string in which I am going to look for a string I will string along";
char *p = "string";
boyer_moore(s, strlen(s), p, strlen(p));
return 0;
}
如预期的那样得到了:
Found string at offset 10: string in which I am going to look for a string I will string along
Found string at offset 51: string I will string along
Found string at offset 65: string along
如果字符串包含两个重叠序列,则两者都被发现:
char *s = "This is an andean andeandean andean trouble";
char *p = "andean";
Found andean at offset 11: andean andeandean andean trouble
Found andean at offset 18: andeandean andean trouble
Found andean at offset 22: andean andean trouble
Found andean at offset 29: andean trouble
为避免重叠匹配,最快的方法是不存储重叠部分。它可以在函数中完成,但这意味着重新初始化第一个增量 vector 并更新字符串指针;我们还需要存储第二个 i
索引为 i2
以防止保存的索引变得非单调。这不值得。更好:
if (j < 0) {
// We have found a patlen match at i+1
// Is it an overlap?
if (index && (indexes[index] + patlen < i+1))
{
// Yes, it is. So we don't store it.
// We could store the last of several overlaps
// It's not exactly trivial, though:
// searching 'anana' in 'Bananananana'
// finds FOUR matches, and the fourth is NOT overlapped
// with the first. So in case of overlap, if we want to keep
// the LAST of the bunch, we must save info somewhere else,
// say last_conflicting_overlap, and check twice.
// Then again, the third match (which is the last to overlap
// with the first) would overlap with the fourth.
// So the "return as many non overlapping matches as possible"
// is actually accomplished by doing NOTHING in this branch of the IF.
}
else
{
// Not an overlap, so store it.
indexes[++index] = i+1;
if (index == max_indexes) // Too many matches already found?
break; // Stop searching and return found so far
}
// Adapt i and j to keep searching
i += patlen + 1;
j = patlen - 1;
continue;
}
关于c++ - 适应 Boyer-Moore 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12702741/
我有一个表类别,它与一对多关系中的任务表相关,我正在尝试使用 Moor 执行连接。 我想返回与类别匹配的任务列表的列表。我该怎么做? Stream> watchAllCategories(
我还没有找到任何关于在 Flutter ORM moor 中内置 Enum 列的可能性的文档。创建枚举列的最佳方法是什么?我想要这个: enum PersistentType { File,
我还没有找到任何关于在 Flutter ORM moor 中内置 Enum 列的可能性的文档。创建枚举列的最佳方法是什么?我想要这个: enum PersistentType { File,
很难说出这里要问什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或夸夸其谈,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开,visit the help center . 关闭 1
很难说出这里要问什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或夸夸其谈,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开,visit the help center . 关闭 1
我对 moor 的依赖: moor_flutter: ^2.1.1 moor_ffi: ^0.4.0 我有表格: netPoint = 关于 netPoint 的信息 netPointNetP
关闭。这个问题是off-topic .它目前不接受答案。 想改善这个问题吗? Update the question所以它是 on-topic对于堆栈溢出。 8 年前关闭。 Improve this
我正在寻找 Moore-Penrose 算法计算伪逆矩阵的 Matlab 实现。 我尝试了几种算法,这个 http://arxiv.org/ftp/arxiv/papers/0804/0804.480
我正在开发一个 flutter 应用程序(当时仅适用于 Android,但计划稍后支持 iOS)。该应用程序以两种方式运行: 具有大部分业务逻辑的 Flutter UI(前台隔离,从 main 方法开
当我执行 update(table).replace(model) 时,我只想更新指定的列它替换与主键对应的所有数据。如何只更新指定的列而不编写自定义查询。 最佳答案 你必须用 Insertable
我正在尝试使用 2D 数组从 boyer moore 实现错误字符规则以进行子字符串搜索,我遇到了我看到我的 arr[0][1] 与 arr[1][0] 重叠的情况这引起了问题。我试图遍历 VS 中的
我正在尝试在大量文本中实现精确的文本搜索。为此,我找到了一些针对 c# 的 Boyer Moore 实现示例,但现在我无法理解它是如何工作的。 例如,如果我有字符串 this is sample te
根据我的理解,找到多数元素的 Boyer-Moore 多数表决算法是 O(1),即它是常数,与输入的大小不成比例。那为什么要wiki link提到对数空间 {\displaystyle O(\log
关于此算法中的两个转换规则(坏字符和好后缀),我有些不明白。他们是否一起工作,以及究竟是什么决定了在每种情况下或轮类中部署哪一个。 This综合解释以 SSIMPLE EXAMPLE 的示例结束,这让
在Boyer-Moore string search algorithm wiki 链接,据说 Boyer-Moore 的最坏情况复杂度是 O(m+n) 如果模式没有出现在文本中 O(mn) 如果模式
我不是专业程序员,所以请多多包涵。我正在四处寻找为什么 haystack 和 needle 的初始“对齐”不应该在 needle 的最后一个字符与 haystack 中的相同字符的第一次一致时进行,但
我正在研究 Boyer-Moore 算法(来自 here),我有一个快速的问题 - 第二遍的需要是什么(它基本上只是通过找到该元素的频率来“确认”)。第一个传递本身不是保证找到的元素是多数元素吗?我考
我将 flutter_moor 用于 SQLite 数据库。我有一个问题,我需要一个 double 的货币金额列,小数点后两位。 我发现有一个 RealColumn,但不知道如何正确实现它。 ///
我即将实现 Boyer-Moore 模式匹配算法的变体(具体来说是星期日算法),我问自己:我的字母表大小是多少? 这取决于编码(= 可能的字符数)还是我可以假设我的字母表包含 256 个符号(= 可以
我在项目中大量使用字符串,因此我正在寻找一个快速的库来处理它们。我认为 Boyer-Moore 算法是最好的。 有免费的解决方案吗? 最佳答案 您可以考虑实现 Boyer–Moore 算法的以下资源:
我是一名优秀的程序员,十分优秀!