在C＃中搜索字节数组中的最长模式
我需要编写有效且快速的方法来搜索给定模式的字节数组。 我这样写，你怎么想，怎么改进？ 它有一个bug，它不能返回长度为1的匹配。
public static bool SearchByteByByte(byte[] bytes, byte[] pattern) { bool found = false; int matchedBytes = 0; for (int i = 0; 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; } 有什么建议 ？
在grep中使用的Boyer-Moore算法非常有效，并且对于更长的模式大小更有效。 我非常确定你可以让它在没有太多困难的情况下使用字节数组，并且它的维基百科页面有一个Java实现，应该很容易移植到C＃。
更新：
这是C＃中字节数组的Boyer-Moore算法的简化版本的实现。 它只使用完整算法的第二个跳转表 。 根据您所说的数组大小（haystack：2000000字节，针：10字节），它比简单的逐字节算法快5-8倍。
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; }
它有一个bug，它不能返回长度为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 = 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; }
更新：这是在讨论和删除局部变量之后的搜索算法（不需要它们）
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; }
因此，您有效地查找最长的公共子字符串，请参阅Wikipedia上的文章： http ： //en.wikipedia.org/wiki/Longest_common_substring_problem
……甚至是参考实现： http ： //en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#C.23 – 当然，你必须在那里用byte[]代替string等。