博耶 - 穆尔-Horspool算法的所有比赛（查看Byte数组里面Byte数组） [英] Boyer-Moore-Horspool Algorithm for All Matches (Find Byte array inside Byte array)

问题描述

下面是我实现BMH算法（它就像一个魅力）的：

 公共静态的Int64的IndexOf（此字节[ ]值，字节[]模式）
 {
如果（价值== NULL）
抛出新的ArgumentNullException（值）; 
 
如果（模式== NULL）
抛出新的ArgumentNullException（模式）; 
 
的Int64 valueLength = value.LongLength; 
的Int64 patternLength = pattern.LongLength; 
 
如果（（valueLength == 0）||（patternLength == 0）||（patternLength> valueLength））
返回-1; 
 
的Int64 [] = badCharacters新的Int64 [256]; 
 
为（Int64的I = 0; I< 256; ++ I）
 badCharacters [I] = patternLength; 
 
的Int64 lastPatternByte = patternLength  -  1; 
 
为（Int64的I = 0; I< lastPatternByte ++ I）
 badCharacters [模式[我] = lastPatternByte  - 我; 
 
 //开始
 
的Int64指数= 0; 
 
，而（指数< =（valueLength  -  patternLength））
 {
为（Int64的I = lastPatternByte;值[（索引+ 1）] ==模式[I] ; --i）
 {
如果（我== 0）
收益指数; 
} 
 
指数+ = badCharacters [值[（+指数lastPatternByte）]; 
} 
 
返回-1; 
} 
  

我试图修改它以此来回报所有的比赛，而不是只第一个指标，但我得到IndexOutOfRangeException无处不在D：

很显然，我失去了一些东西重要还是我没有正确地理解它是如何工作。什么？我做错了。

 公共静态列表<&的Int64 GT; IndexesOf（此字节]值，字节[]模式）
 {
如果（价值== NULL）
抛出新的ArgumentNullException（值）; 
 
如果（模式== NULL）
抛出新的ArgumentNullException（模式）; 
 
的Int64 valueLength = value.LongLength; 
的Int64 patternLength = pattern.LongLength; 
 
如果（（valueLength == 0）||（patternLength == 0）||（patternLength> valueLength））
收益（新的List<&的Int64 GT;（））; 
 
的Int64 [] = badCharacters新的Int64 [256]; 
 
为（Int64的I = 0; I< 256; ++ I）
 badCharacters [I] = patternLength; 
 
的Int64 lastPatternByte = patternLength  -  1; 
 
为（Int64的I = 0; I< lastPatternByte ++ I）
 badCharacters [模式[我] = lastPatternByte  - 我; 
 
 //开始
 
的Int64指数= 0; 
名单，LT; Int64的>指数=新的List<&的Int64 GT;（）; 
 
，而（指数< =（valueLength  -  patternLength））
 {
为（Int64的I = lastPatternByte;值[（索引+ 1）] ==模式[I] ; --i）
 {
如果（我== 0）
 indexes.Add（指数）; 
} 
 
指数+ = badCharacters [值[（+指数lastPatternByte）]; 
} 
 
收益指数; 
} 
  

解决方案

修改

 如果（我== 0）
 indexes.Add（指数）; 
  

到

 如果（我== 0）
 {
 indexes.Add（指数）; 
中断; 
} 
  

Here is my implementation of BMH algorithm (it works like a charm):

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;
}

I tried to modify it in order to return all the matches instead of only the first index, but I'm getting IndexOutOfRangeException everywhere D:

Obviously I'm missing something important or I didn't properly understood how it works. What am I doing wrong?

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;
}

解决方案

Change

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

to

if (i == 0)
{
    indexes.Add(index);
    break;
}

这篇关于博耶 - 穆尔-Horspool算法的所有比赛（查看Byte数组里面Byte数组）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！