泛型KMP算法
泛型KMP算法
当我们需要从一个字符串（主串）中寻找一个模式串（子串）时，使用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()) ;
分类: C#专栏
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did45447