c# 實(shí)現(xiàn)KMP算法的示例代碼
更新時(shí)間：2020年11月23日 08:54:37 作者：溫暖如太陽
這篇文章主要介紹了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)就是通過一個(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#解決SQlite并發(fā)異常問題的方法(使用讀寫鎖)
這篇文章主要介紹了C#解決SQlite并發(fā)異常問題的方法,通過使用讀寫鎖達(dá)到多線程安全訪問,進(jìn)而解決SQLite并發(fā)異常的問題,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2016-07-07
輕松學(xué)習(xí)C#的結(jié)構(gòu)和類
輕松學(xué)習(xí)C#的結(jié)構(gòu)和類，對(duì)C#的結(jié)構(gòu)和類感興趣的朋友可以參考本篇文章，幫助大家更靈活的運(yùn)用C#的結(jié)構(gòu)和類2015-11-11
Winform實(shí)現(xiàn)鼠標(biāo)可穿透的窗體鏤空效果
這篇文章主要介紹了Winform實(shí)現(xiàn)鼠標(biāo)可穿透的窗體鏤空效果的相關(guān)資料,非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2016-10-10
C#實(shí)現(xiàn)的UDP收發(fā)請(qǐng)求工具類實(shí)例
這篇文章主要介紹了C#實(shí)現(xiàn)的UDP收發(fā)請(qǐng)求工具類,結(jié)合具體實(shí)例形式分析了C#針對(duì)UDP請(qǐng)求的監(jiān)聽、接收、發(fā)送等相關(guān)操作技巧,需要的朋友可以參考下2017-06-06
c#入門之實(shí)現(xiàn)簡(jiǎn)易存款利息計(jì)算器示例
這篇文章主要介紹了c#入門之實(shí)現(xiàn)簡(jiǎn)易存款利息計(jì)算器示例,需要的朋友可以參考下2014-04-04
WPF開發(fā)之實(shí)現(xiàn)一種三軸機(jī)械手控件
這篇文章主要為大家詳細(xì)介紹了如何利用WPF實(shí)現(xiàn)簡(jiǎn)單一種三軸機(jī)械手控件，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)或工作有一定幫助，感興趣的小伙伴可以了解一下2023-01-01
這篇文章主要介紹了c# wpf如何使用Blend工具繪制Control樣式，幫助大家更好的理解和學(xué)習(xí)使用c#，感興趣的朋友可以了解下2021-03-03
本文詳細(xì)講解了C#中類與接口的區(qū)別，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-04-04
當(dāng)批處理和aspx不在同一目錄中時(shí)，最好用WorkingDirectory設(shè)置啟動(dòng)的進(jìn)程的初始目錄為批處理所在目錄，否則如上例中批處理新建的目錄就應(yīng)在aspx所在目錄中而不是批處理所在目錄了！2008-12-12
yield?關(guān)鍵字的用途是把指令推遲到程序?qū)嶋H需要的時(shí)候再執(zhí)行，這個(gè)特性允許我們更細(xì)致地控制集合每個(gè)元素產(chǎn)生的時(shí)機(jī)，那么下面就一起來看下怎么用?yield?關(guān)鍵字吧2023-07-07