網(wǎng)站首頁 編程語言 正文
什么是KPM算法
Knuth-Morris-Pratt 字符串查找算法,簡稱為 “KMP算法”,常用于在一個(gè)文本串S內(nèi)查找一個(gè)模式串P 的出現(xiàn)位置,這個(gè)算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年聯(lián)合發(fā)表,故取這3人的姓氏命名此算法。
KMP方法算法就利用之前判斷過信息,通過一個(gè)next數(shù)組,保存模式串中前后最長公共子序列的長度,每次回溯時(shí),通過next數(shù)組找到,前面匹配過的位置,省去了大量的計(jì)算時(shí)間。
KPM的使用場景:模式串在文本串是否出現(xiàn)過,如果出現(xiàn)過,最早出現(xiàn)的位置
步驟
Ⅰ根據(jù)《最大長度表》部分匹配表(next)
對于P = p0 p1 ...pj-1 pj,尋找模式串P中長度最大且相等的前綴和后綴。如果存在p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj,那么在包含pj的模式串中有最大長度為k+1的相同前綴后綴。
舉個(gè)例子,如果給定的模式串為“abab”,那么它的各個(gè)子串的前綴后綴的公共元素的最大長度如下表格所示:
比如對于字符串a(chǎn)ba來說,它有長度為1的相同前綴后綴a;而對于字符串a(chǎn)bab來說,它有長度為2的相同前綴后綴ab(相同前綴后綴的長度為k + 1,k + 1 = 2)。
結(jié)論:最大前綴后綴元素長度所得到的數(shù)組就是我們所需要的 “部分匹配表”
尋找最長前綴后綴
如果給定的模式串是:“ABCDABD”,從左至右遍歷整個(gè)模式串,其各個(gè)子串的前綴后綴分別如下表格所示:
Ⅱ 根據(jù) 部分匹配表 進(jìn)行匹配
匹配失配,j = next [j],模式串向右移動(dòng)的位數(shù)為:j - next[j]。換言之,當(dāng)模式串的后綴pj-k pj-k+1, ..., pj-1跟文本串si-k si-k+1, ..., si-1匹配成功,但pj跟si匹配失敗時(shí),因?yàn)閚ext[j] = k,相當(dāng)于在不包含pj的模式串中有最大長度為k 的相同前綴后綴,即p0 p1 ...pk-1 = pj-k pj-k+1...pj-1,故令j = next[j],從而讓模式串右移j - next[j]位,使得模式串的前綴p0 p1, ..., pk-1對應(yīng)著文本串si-k si-k+1, ..., si-1,而后讓pk跟si繼續(xù)匹配。如下圖所示:
KMP的next數(shù)組相當(dāng)于告訴我們:
當(dāng)模式串中的某個(gè)字符跟文本串中的某個(gè)字符匹配失配時(shí),模式串下一步應(yīng)該跳到哪個(gè)位置。如模式串中在j處的字符跟文本串在i處的字符匹配失配時(shí),下一步用next [j]處的字符繼續(xù)跟文本串i 處的字符匹配,相當(dāng)于模式串向右移動(dòng)j - next[j]位。
代碼實(shí)現(xiàn)
字符串匹配問題:
有一個(gè)字符串 str1=““上海自來水來自海上””,和一個(gè)子串 str2=“自來水”。
現(xiàn)在要判斷str1是否含有str2, 如果存在,就返回第一次出現(xiàn)的位置, 如果沒有,則返回-1
static void Main(string[] args)
{
string str1 = "上海自來水來自海上";
string str2 = "自來水";
// 得出 部分匹配表
int[] next = KPMNext(str2);
// 根據(jù) 得出的 部分匹配表的 next 數(shù)組進(jìn)行匹配,
int index = KPMSearch(str1, str2, next);
Console.WriteLine(index);
}
/// <summary>
/// 獲取一個(gè)字符串的部分匹配值表
/// </summary>
/// <param name="dest"></param>
/// <returns></returns>
static int[] KPMNext(string dest)
{
// 初始化 數(shù)組大小
int[] next = new int[dest.Length];
// 字符串長度為1,部分匹配值就為0
next[0] = 0;
for (int i = 1, j = 0; i < dest.Length; i++)
{
while (j > 0 && dest[i] != dest[j])
{
j = next[j - 1];
}
if (dest[i] == dest[j])
{
j++;
}
next[i] = j;
}
return next;
}
/// <summary>
/// kmp搜索
/// </summary>
/// <param name="str1">源字符串</param>
/// <param name="str2">子字符串</param>
/// <param name="next">部分匹配表</param>
/// <returns></returns>
static int KPMSearch(string str1, string str2, int[] next)
{
for (int i = 0, j = 0; i < str1.Length; i++)
{
while (j > 0 && str1[i] != str2[j])
{
j = next[j - 1];
}
if (str1[i] == str2[j])
{
j++;
}
if (j == str2.Length)
{
return i - j + 1;
}
}
return -1;
}
原文鏈接:https://blog.csdn.net/qq_43562262/article/details/127471917
相關(guān)推薦
- 2022-06-28 C#使用RestClient調(diào)用Web?API_C#教程
- 2022-08-23 Redis?ziplist?壓縮列表的源碼解析_Redis
- 2021-12-03 Android消息機(jī)制Handler深入理解_Android
- 2022-03-28 C++將音頻PCM數(shù)據(jù)封裝成wav文件的方法_C 語言
- 2023-03-20 python如何在pygame中設(shè)置字體并顯示中文詳解_python
- 2022-05-23 NetCat工具命令介紹及遠(yuǎn)程文件傳輸實(shí)現(xiàn)_linux shell
- 2022-09-18 Python中Parser的超詳細(xì)用法實(shí)例_python
- 2022-03-22 .NET?6中間件Http?Logging使用介紹_實(shí)用技巧
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版(
- Linux 中運(yùn)行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符,流程控制 Flo
- 1. Int 和Integer 的區(qū)別,Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤:Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動(dòng)態(tài)字符串(SD
- arthas操作spring被代理目標(biāo)對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列,發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支