數(shù)據(jù)結(jié)構(gòu)–字符串的KMP算法
樸素模式匹配算法：
一旦發(fā)現(xiàn)當(dāng)前這個子串中某個字符不匹配，就只能轉(zhuǎn)而匹配下一個子串(從頭開始)
但我們可以知道：
不匹配的字符之前，一定是和模式串一致的
\color{red}不匹配的字符之前，一定是和模式串一致的
不匹配的字符之前，一定是和模式串一致的
我們可以利用這個信息進(jìn)行優(yōu)化查找，我們知道一定無法匹配的就無需再進(jìn)行匹配操作了
我們可以發(fā)現(xiàn)：
對于模式串T = ‘a(chǎn)baabc’
當(dāng)
第
6
個
\color{red}第6個
第6個元素匹配失敗時，可令主串指針
i
不變
\color{red}i不變
i不變，模式串指針
j
=
3
\color{red}j=3
j=3
當(dāng)
第
5
個
\color{red}第5個
第5個元素匹配失敗時，可令主串指針
i
不變
\color{red}i不變
i不變，模式串指針
j
=
2
\color{red}j=2
j=2
當(dāng)
第
4
個
\color{red}第4個
第4個元素匹配失敗時，可令主串指針
i
不變
\color{red}i不變
i不變，模式串指針
j
=
2
\color{red}j=2
j=2
當(dāng)
第
3
個
\color{red}第3個
第3個元素匹配失敗時，可令主串指針
i
不變
\color{red}i不變
i不變，模式串指針
j
=
1
\color{red}j=1
j=1
當(dāng)
第
2
個
\color{red}第2個
第2個元素匹配失敗時，可令主串指針
i
不變
\color{red}i不變
i不變，模式串指針
j
=
1
\color{red}j=1
j=1
當(dāng)
第
1
個
\color{red}第1個
第1個元素匹配失敗時，匹配下一個相鄰子串，令
j
=
0
,
i
+
+
,
j
+
+
\color{red}j=0, i++, j++
j=0,i++,j++
再來一個Eg：
代碼實(shí)現(xiàn)
typedef struct
{
char ch[15];
int length;
}SString;
int Index_KMP(SString S, SString T, int next[])
{
int i = 1, j = 1;
while (i <= S.length && j <= T.length)
{
if (j == 0 || S.ch[i] == T.ch[j])
i++, j++; //繼續(xù)比較后繼字符
else
j = next[j]; //模式串向右移動
}
if (j > T.length)
return i - T.length;
else
return 0;
}
n e x t 數(shù)組只和短短的模式串有關(guān)，和長長的主串無關(guān) \color{red}next數(shù)組只和短短的模式串有關(guān)，和長長的主串無關(guān) next數(shù)組只和短短的模式串有關(guān)，和長長的主串無關(guān)文章來源：http://www.zghlxwxcb.cn/news/detail-524375.html
時間復(fù)雜度
KMP算法，
最壞時間復(fù)雜度
O
(
m
+
n
)
\color{red}最壞時間復(fù)雜度O(m+n)
最壞時間復(fù)雜度O(m+n)
其中，求next 數(shù)組時間復(fù)雜度O(m)
模式匹配過程最壞時間復(fù)雜度O(n)文章來源地址http://www.zghlxwxcb.cn/news/detail-524375.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--字符串的KMP算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
