当我们需要从一个字符串（主串）中寻找一个模式串（子串）时，使用KMP算法可以极大地提升效率。KMP是一个高效的字符串匹配算法，它巧妙的消除了在匹配的过程中指针回溯的问题，关于KMP算法的更多介绍，可以参考这里。
原始的KMP算法适用的对象是字符串的匹配搜索，其实针对任意类型的串（实际上就是一个数组）的子串搜索，都可以使用KMP算法。比如，我们可能需要在byte[]中查找一个特定的字节数组，这同样可以使用KMP算法来提升匹配性能。为此，我实现了泛型的KMP算法，使之可以应用于任意类型的串匹配。下面是该算法的完整实现。
/// <summary> /// 泛型KMP算法。 /// zhuweisky 2013.06.06 /// </summary> public static class GenericKMP { /// <summary> /// Next函数。 /// </summary> /// <param name="pattern">模式串</param> /// <returns>回溯函数</returns> public static int[] Next<T>(T[] pattern) where T : IEquatable<T> { int[] nextFunction = new int[pattern.Length]; nextFunction[0] = -1; if (pattern.Length < 2) { return nextFunction; } nextFunction[1] = 0; int computingIndex = 2; int tempIndex = 0; while (computingIndex < pattern.Length) { if (pattern[computingIndex - 1].Equals(pattern[tempIndex])) { nextFunction[computingIndex++] = ++tempIndex; } else { tempIndex = nextFunction[tempIndex]; if (tempIndex == -1) { nextFunction[computingIndex++] = ++tempIndex; } } } return nextFunction; } /// <summary> /// KMP计算 /// </summary> /// <param name="source">主串</param> /// <param name="pattern">模式串</param> /// <returns>匹配的第一个元素的索引。-1表示没有匹配</returns> public static int ExecuteKMP<T>(T[] source, T[] pattern) where T : IEquatable<T> { int[] next = Next(pattern); return ExecuteKMP(source, 0, source.Length, pattern, next); } /// <summary> /// KMP计算 /// </summary> /// <param name="source">主串</param> /// <param name="sourceOffset">主串起始偏移</param> /// <param name="sourceCount">被查找的主串的元素个数</param> /// <param name="pattern">模式串</param> /// <returns>匹配的第一个元素的索引。-1表示没有匹配</returns> public static int ExecuteKMP<T>(T[] source, int sourceOffset, int sourceCount, T[] pattern) where T : IEquatable<T> { int[] next = Next(pattern); return ExecuteKMP(source, sourceOffset, sourceCount, pattern, next); } /// <summary> /// KMP计算 /// </summary> /// <param name="source">主串</param> /// <param name="pattern">模式串</param> /// <param name="next">回溯函数</param> /// <returns>匹配的第一个元素的索引。-1表示没有匹配</returns> public static int ExecuteKMP<T>(T[] source, T[] pattern, int[] next) where T : IEquatable<T> { return ExecuteKMP(source, 0, source.Length, pattern, next); } /// <summary> /// KMP计算 /// </summary> /// <param name="source">主串</param> /// <param name="sourceOffset">主串起始偏移</param> /// <param name="sourceCount">被查找的主串的元素个数</param> /// <param name="pattern">模式串</param> /// <param name="next">回溯函数</param> /// <returns>匹配的第一个元素的索引。-1表示没有匹配</returns> public static int ExecuteKMP<T>(T[] source, int sourceOffset, int sourceCount, T[] pattern, int[] next) where T : IEquatable<T> { int sourceIndex = sourceOffset; int patternIndex = 0; while (patternIndex < pattern.Length && sourceIndex < sourceOffset + sourceCount) { if (source[sourceIndex].Equals(pattern[patternIndex])) { sourceIndex++; patternIndex++; } else { patternIndex = next[patternIndex]; if (patternIndex == -1) { sourceIndex++; patternIndex++; } } } return patternIndex < pattern.Length ? -1 : sourceIndex - patternIndex; } }
说明：
（1）串中的每个元素必须能够被比较是否相等，所以，泛型T必须实现IEquatable接口。
（2）之所以将Next函数暴露为public，是为了在外部可以缓存回溯函数，以供多次使用。因为，我们可能经常会在不同的主串中搜索同一个模式串。
（3）如果要将GenericKMP应用于字符串的匹配搜索，可以先将字符串转换为字符数组，再调用GenericKMP算法。就像下面这样：
string source = ".............."; string pattern = "*****"; int index = GenericKMP.ExecuteKMP<char>(source.ToCharArray(),pattern.ToCharArray()) ;
