Look for the longest pattern in a byte array in C #

Question

I need to write an efficient and fast method to find an array of bytes for a given pattern. I write it the way you think how to improve? And he has one error, it cannot return a match with a length of 1.

public static bool SearchByteByByte(byte[] bytes, byte[] pattern) { bool found = false; int matchedBytes = 0; for (int i = 0; i < bytes.Length; i++) { if (pattern[0] == bytes[i] && bytes.Length - i >= pattern.Length) { for (int j = 1; j < pattern.Length; j++) { if (bytes[i + j] == pattern[j]) { matchedBytes++; if (matchedBytes == pattern.Length - 1) { return true; } continue; } else { matchedBytes = 0; break; } } } } return found; } 

Any suggestions?

Answer 1

The Boyer-Moore algorithm used in grep is pretty efficient and more efficient for longer template sizes. I am sure that you can make it work for a byte array without much difficulty, and its page is the second conversion table of the complete algorithm. Based on the size of the arrays you said (haystacks: 2,000,000 bytes, needle: 10 bytes), it is about 5-8 times faster than a simple byte byte algorithm.

  static int SimpleBoyerMooreSearch(byte[] haystack, byte[] needle) { int[] lookup = new int[256]; for (int i = 0; i < lookup.Length; i++) { lookup[i] = needle.Length; } for (int i = 0; i < needle.Length; i++) { lookup[needle[i]] = needle.Length - i - 1; } int index = needle.Length - 1; var lastByte = needle.Last(); while (index < haystack.Length) { var checkByte = haystack[index]; if (haystack[index] == lastByte) { bool found = true; for (int j = needle.Length - 2; j >= 0; j--) { if (haystack[index - needle.Length + j + 1] != needle[j]) { found = false; break; } } if (found) return index - needle.Length + 1; else index++; } else { index += lookup[checkByte]; } } return -1; } 

Answer 2

And he has one error, it cannot return a match with a length of 1

To fix this, start the inner loop from scratch:

 public static bool SearchByteByByte(byte[] bytes, byte[] pattern) { bool found = false; int matchedBytes = 0; for (int i = 0; i < bytes.Length; i++) { if (pattern[0] == bytes[i] && bytes.Length - i >= pattern.Length) { for (int j = 0; j < pattern.Length; j++) // start from 0 { if (bytes[i + j] == pattern[j]) { matchedBytes++; if (matchedBytes == pattern.Length) // remove - 1 return true; continue; } else { matchedBytes = 0; break; } } } } return found; } 

UPDATE: here is your search algorithm after flying and deleting local variables (they are not needed)

 public static bool SearchByteByByte(byte[] bytes, byte[] pattern) { for (int i = 0; i < bytes.Length; i++) { if (bytes.Length - i < pattern.Length) return false; if (pattern[0] != bytes[i]) continue; for (int j = 0; j < pattern.Length; j++) { if (bytes[i + j] != pattern[j]) break; if (j == pattern.Length - 1) return true; } } return false; } 

Answer 3

So, you are looking, effectively, at the longest common substring, so see the Wikipedia article: http://en.wikipedia.org/wiki/Longest_common_substring_problem

... or even a reference implementation: http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#C.23 - you, of course, have to substitute byte[] for string there, etc.