标签: boyer-moore

我整晚都没能为搜索词"anabanana"计算一个简单的移位表,用于Boyer和Moore模式匹配算法.

我找到了以下示例,没有任何解释:

任何人都可以帮助我理解和解释图像查找换档表的方法吗？

要搜索S中的s(size(S)> = size(s)并返回true/false值),使用Apache的StringUtils.contains()或使用Boyer-Moore算法实现和测试的性能更好.我找到的人？

谢谢

我根据这个网站使用过Boyer Moore算法.这仅在文本中实现模式搜索一次,程序退出.有人可以帮我修改这段代码,以便用它们的起始和结束索引多次找到该模式吗？

    public class BoyerMoore {
        private final int R;     // the radix
        private int[] right;     // the bad-character skip array
        private String pat;      // or as a string

        // pattern provided as a string
        public BoyerMoore(String pat) {
            this.R = 256;
            this.pat = pat;

            // position of rightmost occurrence of c in the pattern
            right = new int[R];
            for (int c = 0; c < R; c++)
                right[c] = -1;
            for (int j = 0; j < …

我正在学习字符串搜索算法，并了解它们如何工作，但还没有找到关于在哪种情况下Rabin-Karp算法比KMP或Boyer-Moore更有效的答案。我看到它更容易实现，不需要相同的开销，但是除此之外，我没有任何线索。

那么，什么时候Rabin-Karp比其他更好？

我试图找到str.replace()内置于 python 的时间复杂度，这是我设法收集的数据（在这里和其他网站上）：

我知道replace()是基于 Boyer\xe2\x80\x93Moore 算法，该算法在最坏情况下需要 O(n*m) 时间来查找子字符串，但这适用于单个子字符串吗？

当找到第一个子字符串然后再次开始搜索时，是否replace()返回“固定”字符串的副本？

当子字符串多次出现时该怎么办，如下例所示：

old_string = '192.168.1.1'\nnew_string = old_string.replace('.', '|')\n

如果它一次只能替换一个子串，那么对于单个子串，我们得到 O(n*m)，乘以子串的数量，最大为 n/m。这就是 O(n^2)！

假设一个简单的循环需要 O(n)，例如：

old_string = '192.168.1.1'\nnew_string = []\nfor ch in old_string:\n    new_string.append('|' if ch == '.' else ch)\n

那有意义吗？我错过了什么吗？

内置的replace()对于多次替换是否存在缺陷，或者它的实现方式是从中断处继续吗？

我正在尝试编写没有前缀函数的博耶摩尔算法的更简单版本。它必须打印与模式进行比较的符号的所有位置。在本地它通过了测试，但是当我将其提交到gitlab时它失败了。我在这里无法发现未定义的行为。我最后有垃圾。

#include <stdio.h>

#define MAX_PATTERN_LEN 16
#define BUF_SIZE 69
#define ALPH_SIZE 128

int read_str(int max_len, unsigned char *str_place) {
    int count_read = 0;
    for (int i = 0, ch; i < max_len; i++) {
        if ((ch = getchar()) == '\n') {
            str_place[i] = '\0';
            break;
        }
        str_place[i] = (char)ch;
        count_read++;
    }
    return count_read;
}

void calculate_shifts(const unsigned char *str, int len_str, int *badchar) {
    for (int i = 0; i < ALPH_SIZE; i++)
        badchar[i] = len_str;
    for (int i = …

我无法理解 Horspool 在他的算法中所做的更改。如果您有 Boyer-Moore-Horspool 算法的任何链接，请告诉我。