C#,字符串匹配(模式搜索)KMP算法的源代码与数据可视化
2024-01-10 11:10:28
?D.E.Knuth
?J.H.Morris
一、KMP算法
KMP 算法(Knuth-Morris-Pratt 算法)是其中一个著名的、传统的字符串匹配算法,效率比较高。
KMP算法由D.E.Knuth,J.H.Morris和V.R.Pratt在 Brute-Force算法的基础上提出的模式匹配的改进算法。因此人们称它为“克努特—莫里斯—普拉特算法”,简称KMP算法。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时,主串的比较位置需要回退。KMP算法在上述情况下,主串位置不需要回退,从而可以大大提高效率。
要点:实现方法主要是通过一个LPS(Longest Proper Suffix)数组实现,数组本身包含了模式串的局部匹配信息。
KMP算法的时间复杂度为O(m+n)?。
有些人以为讲清楚了,其实没有。
学习算法,阅读文字浪费时间,看图及阅读代码最好。
下载Visual Studio 2022工程包https://download.csdn.net/download/beijinghorn/85090446
二、运行效果
本文源代码的运行效果:
三、核心代码
using System;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
/// <summary>
/// 字符串匹配(模式搜索)算法集锦
/// </summary>
public static partial class PatternSearch
{
/// <summary>
/// 字符串匹配的KMP算法
/// </summary>
/// <param name="text"></param>
/// <param name="pattern"></param>
public static List<int> KMP_Search(string text,string pattern)
{
List<int> matchs = new List<int>();
int M = pattern.Length;
int N = text.Length;
int[] lps = new int[M];
int j = 0;
Build_LPS_Array(pattern, M, lps);
int i = 0;
while (i < N)
{
if (pattern[j] == text[i])
{
j++;
i++;
}
if (j == M)
{
matchs.Add(i - j);
j = lps[j - 1];
}
else if (i < N && pattern[j] != text[i])
{
if (j != 0)
{
j = lps[j - 1];
}
else
{
i = i + 1;
}
}
}
return matchs;
}
/// <summary>
/// 构造 LPS 数组
/// 最长后缀数组,Longest Proper Suffix
/// </summary>
/// <param name="pattern"></param>
/// <param name="M"></param>
/// <param name="lps"></param>
private static void Build_LPS_Array(string pattern, int M, int[] lps)
{
lps[0] = 0;
int len = 0;
int i = 1;
while (i < M)
{
if (pattern[i] == pattern[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0)
{
len = lps[len - 1];
}
else
{
lps[i] = len;
i++;
}
}
}
}
}
}
四、改进KMP算法
软件的改进无非是用存储换计算。
保存更多的相邻信息,就可以提高计算速度。
---------------------------------------------
POWER BY TRUFFER.CN
文章来源:https://blog.csdn.net/beijinghorn/article/details/124000700
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!