泛型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
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
当前名称:泛型KMP算法-创新互联
网页链接:http://myzitong.com/article/csices.html