泛型KMP算法-创新互联

当我们需要从一个字符串（主串）中寻找一个模式串（子串）时，使用KMP算法可以极大地提升效率。KMP是一个高效的字符串匹配算法，它巧妙的消除了在匹配的过程中指针回溯的问题，关于KMP算法的更多介绍，可以参考这里。

原始的KMP算法适用的对象是字符串的匹配搜索，其实针对任意类型的串（实际上就是一个数组）的子串搜索，都可以使用KMP算法。比如，我们可能需要在byte[]中查找一个特定的字节数组，这同样可以使用KMP算法来提升匹配性能。为此，我实现了泛型的KMP算法，使之可以应用于任意类型的串匹配。下面是该算法的完整实现。

/// 

    /// 泛型KMP算法。
    /// zhuweisky 2013.06.06
    /// 
    public static class GenericKMP
    {
        /// 

        /// Next函数。
        /// 
        /// 模式串
        /// 回溯函数
        public static int[] Next(T[] pattern) where T : IEquatable
        {
            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;
        }
        /// 

        /// KMP计算
        /// 
        /// 主串      
        /// 模式串
        /// 匹配的第一个元素的索引。-1表示没有匹配
        public static int ExecuteKMP(T[] source, T[] pattern) where T : IEquatable
        {
            int[] next = Next(pattern);
            return ExecuteKMP(source, 0, source.Length, pattern, next);
        }
        /// 

        /// KMP计算
        /// 
        /// 主串
        /// 主串起始偏移
        /// 被查找的主串的元素个数
        /// 模式串
        /// 匹配的第一个元素的索引。-1表示没有匹配
        public static int ExecuteKMP(T[] source, int sourceOffset, int sourceCount, T[] pattern) where T : IEquatable
        {
            int[] next = Next(pattern);
            return ExecuteKMP(source, sourceOffset, sourceCount, pattern, next);
        }
        /// 

        /// KMP计算
        /// 
        /// 主串      
        /// 模式串
        /// 回溯函数
        /// 匹配的第一个元素的索引。-1表示没有匹配
        public static int ExecuteKMP(T[] source, T[] pattern, int[] next) where T : IEquatable
        {           
            return ExecuteKMP(source, 0, source.Length, pattern, next);
        }
        /// 

        /// KMP计算
        /// 
        /// 主串
        /// 主串起始偏移
        /// 被查找的主串的元素个数
        /// 模式串
        /// 回溯函数
        /// 匹配的第一个元素的索引。-1表示没有匹配
        public static int ExecuteKMP(T[] source, int sourceOffset, int sourceCount, T[] pattern, int[] next) where T : IEquatable
        {
            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(source.ToCharArray(),pattern.ToCharArray()) ;

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。