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