C#,字符串匹配(模式搜索)KMP算法的源代码与数据可视化

2024-01-10 11:10:28

?D.E.Knuth

?J.H.Morris

一、KMP算法

KMP 算法(Knuth-Morris-Pratt 算法)是其中一个著名的、传统的字符串匹配算法,效率比较高。

KMP算法由D.E.KnuthJ.H.MorrisV.R.PrattBrute-Force算法的基础上提出的模式匹配的改进算法。因此人们称它为“克努特—莫里斯—普拉特算法”,简称KMP算法。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时,主串的比较位置需要回退。KMP算法在上述情况下,主串位置不需要回退,从而可以大大提高效率。

要点:实现方法主要是通过一个LPS(Longest Proper Suffix)数组实现,数组本身包含了模式串的局部匹配信息。

KMP算法的时间复杂度为O(m+n)?。

有些人以为讲清楚了,其实没有。

学习算法,阅读文字浪费时间,看图及阅读代码最好。

下载Visual Studio 2022工程包icon-default.png?t=N7T8https://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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。