c# 實現(xiàn)KMP算法的示例代碼
更新時間：2020年11月23日 08:54:37 作者：溫暖如太陽
這篇文章主要介紹了c# 實現(xiàn)KMP算法的示例代碼，幫助大家更好的理解和使用c#，感興趣的朋友可以了解下
KMP算法是一種改進的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡稱KMP算法）。KMP算法的核心是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達到快速匹配的目的。具體實現(xiàn)就是通過一個next()函數(shù)實現(xiàn)，函數(shù)本身包含了模式串的局部匹配信息。KMP算法的時間復(fù)雜度O(m+n) 。
實現(xiàn)方式就不再這里獻丑了，網(wǎng)上很多講解，此處只是記錄下c#實現(xiàn)的代碼。
public class KMP
{
public static int[] GetNext(String ps)
{
char[] p = ps.ToArray();
int[] next = new int[p.Length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.Length - 1)
{
if (k == -1 || p[j] == p[k])
{
next[++j] = ++k;
}
else
{
k = next[k];
}
}
return next;
}
public static int GetIndex(String ts, String ps)
{
char[] t = ts.ToArray();
char[] p = ps.ToArray();
int i = 0; // 主串的位置
int j = 0; // 模式串的位置
int[] next = GetNext(ps);
while (i < t.Length && j < p.Length)
{
if (j == -1 || t[i] == p[j])
{
// 當(dāng)j為-1時，要移動的是i，當(dāng)然j也要歸0
i++;
j++;
}
else
{
// i不需要回溯了
// i = i - j + 1;
j = next[j]; // j回到指定位置
}
}
if (j == p.Length)
{
return i - j;
}
else
{
return -1;
}
}
}
//test
static void Main(string[] args)
{
Console.WriteLine( KMP.GetIndex("abcdbcxdbc", "dbc"));
Console.ReadKey();
}
以上就是c# 實現(xiàn)KMP算法的示例代碼的詳細內(nèi)容，更多關(guān)于c# kmp算法的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了C#拷貝文件簡單實現(xiàn)方法,主要分析了FileInfo類中CopyTo方法針對文件復(fù)制的操作技巧,非常簡單實用,需要的朋友可以參考下2015-04-04
在C#中,ContextMenuStrip是一種用于創(chuàng)建右鍵菜單的控件,它提供了一種方便的方式來為特定的控件或窗體添加自定義的上下文菜單選項,有兩種實現(xiàn)方式,文中介紹的非常詳細,需要的朋友可以參考下2024-03-03
本文主要介紹了C#中?、?.、??、??=運算符的用法，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
這篇文章主要介紹了C#自動判斷Excel版本使用不同的連接字符串,本文重點在不同版本的連接字符串介紹,需要的朋友可以參考下2015-06-06
這篇文章主要介紹了C#異步編程由淺入深(三)之詳解Awaiter,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-03-03
Unity 2017使用UGUI實現(xiàn)大轉(zhuǎn)盤抽獎
這篇文章主要為大家詳細介紹了Unity 2017使用UGUI實現(xiàn)大轉(zhuǎn)盤抽獎，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-02-02
C#實現(xiàn)給DataGrid單元行添加雙擊事件的方法
這篇文章主要介紹了C#實現(xiàn)給DataGrid單元行添加雙擊事件的方法,較為詳細的分析了C#給DataGrid單元添加雙擊事件的步驟及相關(guān)實現(xiàn)代碼,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
2048是一款數(shù)字益智游戲，初始數(shù)字則是由2+2組成的基數(shù)4。在操作方面的不同則表現(xiàn)為一步一格的移動，變成更為爽快的一次到底。相同數(shù)字的方?jīng)r在靠攏、相撞時會相加。本文將通過Unity3D實現(xiàn)這一游戲，需要的可以參考一下2022-03-03
本篇文章主要介紹了C# 創(chuàng)建壓縮文件的實現(xiàn)代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05
這篇文章主要介紹了C#獲取哈希加密生成隨機安全碼的類,涉及C#哈希加密及字符串操作的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-03-03