KMP算法的实现
2024-10-18 03:41:40
今天看到了一篇关于KMP算法的讲解的文章，很难得，讲得非常清楚。分享给大家，希望对大家有帮助。http://kb.cnblogs.com/page/176818/
我自己基于这个讲解的内容作了一个实现，效果还不错，码代码的功力有限，还请大家多指正其中可以改进的地方。
using System.Collections.Generic; namespace KMPImplementation
{
/// <summary>
/// 该类用于生成KMP算法中，需要用的部分匹配表
/// </summary>
public class PartialMatchTable
{
private string data;
List<int> OffsetArray = new List<int>(); /// <summary>
/// 在构造函数中获得匹配模式，并计算产生部分匹配表
/// </summary>
/// <param name="para"></param>
public PartialMatchTable(string para)
{
data = para;
GenerateOffsetArray();
} /// <summary>
/// 计算一个字符串中，最长的相同前缀与后缀的长度
/// </summary>
/// <param name="str">需要计算的字符串</param>
/// <returns>长度值</returns>
private int GetMaxPrefixPostfixLength(string str)
{
int cnt = ;
if (str != null)
{
int len = str.Length - ;
for (int i = ; i <= len; i++)
{
string pre = str.Substring(, i);
string post = str.Substring(str.Length - i, i);
if (pre == post)
cnt = cnt < i ? i : cnt;
}
}
return cnt;
} /// <summary>
/// 计算给定字符串各个字符对应的偏移值
/// </summary>
private void GenerateOffsetArray()
{
if (string.IsNullOrEmpty(data))
return;
if (data.Length == )
return;
for (int i = ; i < data.Length; i++)
{
string sub = data.Substring(, i + );
int max = GetMaxPrefixPostfixLength(sub);
OffsetArray.Add(max);
}
} /// <summary>
/// 从部分匹配表中，取出相应的值
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public int GetOffset(int i)
{
int val = ;
if (OffsetArray.Count > i)
val = OffsetArray[i];
return val;
} /// <summary>
/// 调试用的，打印计算结果
/// </summary>
public void PrintDic()
{
int cnt = data.Length;
for (int i = ; i < cnt; i++)
{
System.Diagnostics.Debug.WriteLine("{0},{1}\n", data[i], OffsetArray[i]);
}
}
}
}
using System.Collections.Generic; namespace KMPImplementation
{
/// <summary>
/// 该类实现了KMP匹配算法，以此在目标串中查找匹配模式的index
/// </summary>
public class KMPImplementation
{
private string pattern; // 记录模式
private string data;// 记录目标串
PartialMatchTable si;// 记录部分匹配表 /// <summary>
/// 在构造函数中，将异常的输入，如null，过滤处理
/// </summary>
/// <param name="dt">需要匹配的目标串</param>
/// <param name="ptn">匹配模式</param>
public KMPImplementation(ref string dt, string ptn)
{
si = new PartialMatchTable(ptn);
if (dt == null || ptn == null)
{
data = string.Empty;
pattern = string.Empty;
}
else
{
data = dt;
pattern = ptn;
}
} /// <summary>
/// 查找目标串中的第一个匹配项的index
/// </summary>
/// <returns></returns>
public int FindFirstIndex()
{
int idx = -;
int datalen = data.Length;
int patternlen = pattern.Length;
// 空串查找空串的情况
if (datalen == patternlen && patternlen == )
return ;
// 对应目标串比模式短的情况，直接返回找不到，即是-1
if (datalen >= patternlen)
{
datalen = datalen - patternlen;
for (int i = ; i <= datalen; )
{
for (int j = ; j < patternlen; )
{
if (data[i + j] == pattern[j])// 模式与目标串的字符相同，继续比较下一个
{
j++;
if (j == patternlen)// 当模式的index指到了最后一个位置，表明查找到了
return i;
}
else// 当模式与目标串不匹配时
{
if (j == )// 如果第一个字符都不匹配，继续比较下一个位置
i++;
else
i += j - si.GetOffset(j - );// 如果已经发生了部分匹配，查找部分匹配表来确定，当前应该将目标串的index向后移动的量
break;
}
}
}
}
return idx;
} /// <summary>
/// 查找目标串中的所有匹配项的index，以List形式返回
/// </summary>
/// <returns></returns>
public List<int> FindAllIndex()
{
List<int> list = new List<int>();
int datalen = data.Length;
int patternlen = pattern.Length;
// 空串查找空串的情况
if (datalen == patternlen && patternlen == )
{
list.Add();
return list;
}
// 对应目标串比模式短的情况，直接返回找不到，即是-1
if (datalen >= patternlen)
{
datalen = datalen - patternlen;
for (int i = ; i <= datalen; )
{
for (int j = ; j < patternlen; )
{
if (data[i + j] == pattern[j])// 模式与目标串的字符相同，继续比较下一个
{
j++;
if (j == patternlen)// 当模式的index指到了最后一个位置，表明查找到了
{
list.Add(i);
i++;
}
}
else// 当模式与目标串不匹配时
{
if (j == )// 如果第一个字符都不匹配，继续比较下一个位置
i++;
else
i += j - si.GetOffset(j - );// 如果已经发生了部分匹配，查找部分匹配表来确定，当前应该将目标串的index向后移动的量
break;
}
}
}
}
if (list.Count == )
list.Add(-);
return list;
}
}
}
这里实现了两个方法，一个是查找第一个匹配项，一个是查找所有的匹配项，方便调用；但是，显而易见的是，两个方法有太多的相同的地方，可以再做一次抽象。懒病犯了，就没接着改进了。
最新文章
- JavaScript学习笔记-函数
- Android Studio 经常使用功能介绍
- 13.C#分部类型和静态类(七章7.1-7.2)
- Android中直播视频技术探究之---摄像头Camera视频源数据采集解析
- Python--类定义
- ASP.NET实例——漂亮的自适应宽度的导航条（仿Discuz!）
- Spring IoC — 基于XML的配置
- 解决MySQL不允许从远程访问的方法
- vijosP1092 全排列
- XMPP通讯开发-好友获取界面设计
- asp.net下用js实现弹出子窗口选定值并返回
- listview改变选中行字体颜色
- 使用jsCompress压缩混淆js代码的一些常见的问题和技巧
- VB6工程在Win10系统打开提示MSCOMCTL.OCX无法加载
- 偶发异常BUG，如何高效精准分析排查定位？
- 3.django Model
- git关联远程仓库
- CNUTCon2017全球运维技术大会（持续更新中） - 斯达克学院 - 实战驱动的 IT 教育平台 - Powered By EduSoho
- 封装jsonp
- leveldb开篇