?D.E.Knuth

?J.H.Morris

一、KMP算法

KMP 算法（Knuth-Morris-Pratt 算法）是其中一個(gè)著名的、傳統(tǒng)的字符串匹配算法，效率比較高。

KMP算法由D.E.Knuth，J.H.Morris和V.R.Pratt在 Brute-Force算法的基礎(chǔ)上提出的模式匹配的改進(jìn)算法。因此人們稱它為“克努特—莫里斯—普拉特算法”，簡(jiǎn)稱KMP算法。KMP算法的核心是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。Brute- Force算法在模式串中有多個(gè)字符和主串中的若干個(gè)連續(xù)字符比較都相等，但最后一個(gè)字符比較不相等時(shí)，主串的比較位置需要回退。KMP算法在上述情況下,主串位置不需要回退，從而可以大大提高效率。

要點(diǎn)：實(shí)現(xiàn)方法主要是通過(guò)一個(gè)LPS（Longest Proper Suffix）數(shù)組實(shí)現(xiàn)，數(shù)組本身包含了模式串的局部匹配信息。

KMP算法的時(shí)間復(fù)雜度為O(m+n)?。

有些人以為講清楚了，其實(shí)沒(méi)有。

學(xué)習(xí)算法，閱讀文字浪費(fèi)時(shí)間，看圖及閱讀代碼最好。

下載Visual Studio 2022工程包https://download.csdn.net/download/beijinghorn/85090446

二、運(yùn)行效果

本文源代碼的運(yùn)行效果：

三、核心代碼

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>
		/// 構(gòu)造 LPS 數(shù)組
		/// 最長(zhǎng)后綴數(shù)組，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++;
					}
				}
			}
		}
	}
}

四、改進(jìn)KMP算法

軟件的改進(jìn)無(wú)非是用存儲(chǔ)換計(jì)算。

保存更多的相鄰信息，就可以提高計(jì)算速度。

---------------------------------------------
POWER BY TRUFFER.CN文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-822788.html

到了這里，關(guān)于C#，字符串匹配（模式搜索）KMP算法的源代碼與數(shù)據(jù)可視化的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！