-
kmp算法
鎖定
- 應 用
- 字符串匹配 [1]
- 發現者
- D.E.Knuth等 [1]
- 時間複雜度
- O（m+n） [1]
kmp算法簡介
KMP算法是三位學者在 Brute-Force算法的基礎上同時提出的模式匹配的改進算法。Brute- Force算法在模式串中有多個字符和主串中的若干個連續字符比較都相等,但最後一個字符比較不相等時,主串的比較位置需要回退。KMP算法在上述情況下,主串位置不需要回退,從而可以大大提高效率
[2]
。
kmp算法字符串的模式匹配
字符串的模式匹配是一種常用的運算。所謂模式匹配,可以簡單地理解為在目標(字符串)中尋找一個給定的模式(也是字符串)，返回目標和模式匹配的第一個子串的首字符位置。通常目標串比較大，而模式串則比較短小
[3]
。
kmp算法模式匹配的類型
(1)精確匹配
如果在目標T中至少一處存在模式P，則稱匹配成功，否則即使目標與模式只有一個字符不同也不能稱為匹配成功，即匹配失敗。給定一個字符或符號組成的字符串目標對象T和一個字符串模式P，模式匹配的目的是在目標T中搜索與模式P完全相同的子串,返回T和P匹配的第一個字符串的首字母位置
[3]
。
(2)近似匹配
kmp算法KMP模式匹配算法
求得模式的特徵向量之後，基於特徵分析的快速模式匹配算法(KMP模式匹配算法)與樸素匹配算法類似，只是在每次匹配過程中發生某次失配時，不再單純地把模式後移一位，而是根據當前字符的特徵數來決定模式右移的位數
[3]
。
#include "string. h"
#include<assert. h>
int KMPStrMatching(String T, String P, int. N, int startIndex)
{int lastIndex=T.strlen() -P.strlen();
if((1 astIndex- startIndex)<0)//若 startIndex過大,則無法匹配成功
return (-1);//指向P內部字符的遊標
int i;//指向T內部字符的遊標
int j=0;//指向P內部字符的遊標
for(i= startIndex; i <T.strlen(); i++)
{while(P[j]!=T[i]&& j>0)
j=N[j-1];
if(P[j]==T[i])
j++;
if(j ==P.strlen())
return(1-j+1);//匹配成功,返回該T子串的開始位置
}
return (-1);
}
