A C# implementation of the Boyer-Moore-Horspool algorithm.
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; | |
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; | |
} | |
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; | |
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); | |
break; | |
} | |
} | |
index += badCharacters[value[(index + lastPatternByte)]]; | |
} | |
return indexes; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment