目錄
一、樸素的模式匹配演算法
二、KMP演算法（改進的模式匹配演算法）
hello！大家好哇，我是灰小猿，一個超會寫bug的沙雕程式猿！
今天來和大家分享一個關于字串比較的模式匹配演算法，在資料結構中對字串的相關操作中，對子串的定位操作通常稱為串的模式匹配，同樣他也是各種串處理中最重要的操作之一，同時子串也稱為模式串，關于主串和模式串的匹配演算法常用的主要有兩種：樸素的模式匹配演算法和KMP演算法（改進的模式匹配演算法），接下來將分別對這兩種演算法進行分析，
一、樸素的模式匹配演算法
樸素的模式匹配演算法也被稱為布魯特—福斯演算法，其基本思想是：從主串的第一個字符起與模式串的第一個字符相比較，若相等，則逐一對之后的字符進行比較，否則從主串的第二個字符與模式串的第一個字符重新比較，直到模式串中的每一個字符依次與主串中連續的字符序列相匹配為止，這時就稱為匹配成功，如果不能在主串中找到與模式串相匹配的內容，則稱為匹配失敗，
接下來舉一個例子，以字符陣列存盤字串，實作樸素的模式匹配演算法，
//傳入主串s和模式串t，同時設定從主串中開始匹配的位置pos
int index(char s[],char t[],int pos) {
int i,j,slen,tlen;
i = pos;
j = 0;
slen = s.length; //獲取到主串的長度
tlen = t.length; //獲取到模式串的長度
while (i<slen && j<tlen) {
if (s[i] == t[j]) {
i++;
j++;
}
else {
i = i-j+1;
j=0;
}
}
if (j>=tlen) {
return i-tlen;
}
return 1;
}
二、KMP演算法（改進的模式匹配演算法）
KMP演算法是上一個演算法的改進，相比于樸素的模式匹配演算法，KMP演算法在進行主串和模式串的匹配程序中，每當匹配程序中出現相比較的字符不相等時，不需要回退主串的字符位置指標，而是利用已經得到的“部分匹配”結果將模式串向右“滑動”盡可能遠的距離，再繼續進行比較，
設模式串為“P0...P(m-1)”,KMP匹配演算法的思想是：當模式串中的字符Pj與主串中相應的字符Si不相等時，因其前j個字符（“P0...P(j-1)”）已經獲得了成功的匹配，所以若模式串中的“P0...P(k-1)”與“P(j-k)...P(j-1)”相同，這時可令P0與Si相比較，從而使i無需回退，
在KMP演算法中，依據模式串的next函式值可以實作子串的滑動，若令next[j]=k，則next[j]表示當模式串中的Pj與主串中相應的字符不相等時，令模式串的Pnext[j]與主串的相應字符進行比較，
關于next函式有如下的定義：
以下是求模式串的next函式的程式：
//求模式串p的next函式值，并存入陣列next中
void Get_next(char *p,int next[])
{
int i,j,slen;
slen = strlen(p); //獲取到模式串的長度
i=0;
while (i<slen) {
if (j==-1||p[i]==p[j]) {
++i;
++j;
next[i] = j;
} else {
j = next[j];
}
}
}
在獲取到的next函式后，
在KMP模式匹配演算法中，設模式串的第一個字符下標為0，則KMP演算法如下：
/*利用模式串p的next函式，求p在主串s中從第pos個字符開始的位置*/
/*若匹配成功，回傳模式串在主串的位置下標，否則回傳-1 */
int Index_KMP(char *s,char *p,int pos,int next[])
{
int i,j,slen,plen;
i=pos-1;
j=-1;
slen = strlen(s); //求主串的長度
plen = strlen(p); //求模式串的長度
while (i<slen && j<plen) {
if (j==-1||s[i]==p[j]) {
++i;
++j;
} else {
j=next[j];
}
}
if (j>=plen) {
return i-plen;
}
else {
return -1
}
}
關于字串模式匹配演算法就分享到這里，有不足的地方還希望各位大佬一起指正，
覺得不錯記得點贊關注喲！
大灰狼陪你一起進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/3247.html
標籤：其他