泛型KMP算法代码,C#代码库,德仔网

代码语言
代码分类
【C#】泛型KMP算法
作者:筱雨 / 发布于2017/2/23/ 635
当我们需要从一个字符串（主串）中寻找一个模式串（子串）时，使用KMP算法可以极大地提升效率。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()) ;
试试其它关键字
同语言下
可能有用的
筱雨贡献的其它代码(28)