代码语言
.
CSharp
.
JS
Java
Asp.Net
C
MSSQL
PHP
Css
PLSQL
Python
Shell
EBS
ASP
Perl
ObjC
VB.Net
VBS
MYSQL
GO
Delphi
AS
DB2
Domino
Rails
ActionScript
Scala
代码分类
文件
系统
字符串
数据库
网络相关
图形/GUI
多媒体
算法
游戏
Jquery
Extjs
Android
HTML5
菜单
网页交互
WinForm
控件
企业应用
安全与加密
脚本/批处理
开放平台
其它
【
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()) ;
试试其它关键字
同语言下
.
C#实现的html内容截取
.
C#动态修改文件夹名称(FSO实现,不移动文件)
.
c# 移动文件或文件夹
.
c#图片添加水印
.
网站后台修改图片尺寸代码
.
处理大图片在缩略图时的展示
.
实现对图片上传的接收
.
去除字符串中的空格,回车,换行符转变成‘;’在按‘
.
按照回车换行符分割字符串
.
文件MD5码 比较,检测文件是否一样
可能有用的
.
C#实现的html内容截取
.
C#动态修改文件夹名称(FSO实现,不移动文件)
.
c# 移动文件或文件夹
.
c#图片添加水印
.
网站后台修改图片尺寸代码
.
处理大图片在缩略图时的展示
.
实现对图片上传的接收
.
去除字符串中的空格,回车,换行符转变成‘;’在按‘
.
按照回车换行符分割字符串
.
文件MD5码 比较,检测文件是否一样
筱雨
贡献的其它代码
(
28
)
.
查看存储过程修改时间,最近执行时间
.
json下钻函数,解决多层嵌套问题
.
向上公告走马灯
.
JAVA发送HttpClient请求及接收请求结果过程
.
根据图片在ftp路径获取InputStream流
.
断点续传(springMvc),可支持html5在线播放
.
IE提交表单记录历史,点击返回信息仍在。
.
用SQOOP从SQLSERVER导入数据到(HDFS,HIVE,HBASE)
.
泛型KMP算法
.
iframe框架根据内容自动伸缩高度
Copyright © 2004 - 2024 dezai.cn. All Rights Reserved
站长博客
粤ICP备13059550号-3