所有匹配的Boyer-Moore-Horspool算法(在字节数组中查找字节数组)

本文关键字：字节数 字节 数组 查找 算法 Boyer-Moore-Horspool | 更新日期: 2023-09-27 18:11:12

这是我的BMH算法的实现(它像一个魅力一样工作):

public static Int64 IndexOf(this Byte[] value, Byte[] pattern)
{
    if (value == null)
        throw new ArgumentNullException("value");
    if (pattern == null)
        throw new ArgumentNullException("pattern");
    Int64 valueLength = value.LongLength;
    Int64 patternLength = pattern.LongLength;
    if ((valueLength == 0) || (patternLength == 0) || (patternLength > valueLength))
        return -1;
    Int64[] badCharacters = new Int64[256];
    for (Int64 i = 0; i < 256; ++i)
        badCharacters[i] = patternLength;
    Int64 lastPatternByte = patternLength - 1;
    for (Int64 i = 0; i < lastPatternByte; ++i)
        badCharacters[pattern[i]] = lastPatternByte - i;
    // Beginning
    Int64 index = 0;
    while (index <= (valueLength - patternLength))
    {
        for (Int64 i = lastPatternByte; value[(index + i)] == pattern[i]; --i)
        {
            if (i == 0)
                return index;
        }
        index += badCharacters[value[(index + lastPatternByte)]];
    }
    return -1;
}

我试图修改它，以返回所有的匹配，而不是只有第一个索引，但我得到IndexOutOfRangeException无处不在D:

显然我遗漏了一些重要的东西，或者我没有正确理解它是如何工作的。我做错了什么?

public static List<Int64> IndexesOf(this Byte[] value, Byte[] pattern)
{
    if (value == null)
        throw new ArgumentNullException("value");
    if (pattern == null)
        throw new ArgumentNullException("pattern");
    Int64 valueLength = value.LongLength;
    Int64 patternLength = pattern.LongLength;
    if ((valueLength == 0) || (patternLength == 0) || (patternLength > valueLength))
        return (new List<Int64>());
    Int64[] badCharacters = new Int64[256];
    for (Int64 i = 0; i < 256; ++i)
        badCharacters[i] = patternLength;
    Int64 lastPatternByte = patternLength - 1;
    for (Int64 i = 0; i < lastPatternByte; ++i)
        badCharacters[pattern[i]] = lastPatternByte - i;
    // Beginning
    Int64 index = 0;
    List<Int64> indexes = new List<Int64>();
    while (index <= (valueLength - patternLength))
    {
        for (Int64 i = lastPatternByte; value[(index + i)] == pattern[i]; --i)
        {
            if (i == 0)
                indexes.Add(index);
        }
        index += badCharacters[value[(index + lastPatternByte)]];
    }
    return indexes;
}

所有匹配的Boyer-Moore-Horspool算法(在字节数组中查找字节数组)

变化

if (i == 0)
    indexes.Add(index);


if (i == 0)
{
    indexes.Add(index);
    break;
}
相关文章：