前言
眾所周知盖腿，字符串匹配暴力方法時間復(fù)雜度過大。經(jīng)典的看毛片算法(KMP)算法，使用預(yù)處理的手段和后綴前綴特征以及遞歸思想失都，可以大幅度優(yōu)化字符串匹配時間復(fù)雜度后控。
KMP算法思路
- KMP就是每回模式串移動的不是一個單位移動庙曙，而是將前面匹配的都移動使得首部對應(yīng)被匹配的字符串對應(yīng)位置。也即是模式串得移動等同模式串移動塊大小的位置浩淘。
- 模式串移動塊即字符串后綴與字符串前綴的最大共同部分捌朴。
- 利用遞歸的思路預(yù)處理求解模式串移動塊 從第一個位置開始循環(huán) ，標(biāo)記為q张抄，當(dāng)k位置的元素不等于q位置的元素砂蔽，k遞歸為next[k-1],相等時k后移，使得next[q]=k;
-
跟據(jù)next數(shù)組進行移動模式串欣鳖，遞歸求解察皇。
KMP模式串移動塊.png
實現(xiàn)代碼
預(yù)處理next數(shù)組
void makeNext(const char P[],int next[])
{
int q,k; //聲明變量
int m = strlen(P);
next[0] = 0;
for (q = 1,k = 0; q < m; ++q)
{
//while語句 遞歸求解
while(k > 0 && P[q] != P[k])
k = next[k-1];
//相等后移
if (P[q] == P[k])
{
k++;
}
//賦值
next[q] = k;
}
}
KMP核心代碼
int kmp(const char T[],const char P[],int next[])
{
int n,m;
int i,q;
n = strlen(T);
m = strlen(P);
makeNext(P,next);
for (i = 0,q = 0; i < n; ++i)
{
while(q > 0 && P[q] != T[i])
q = next[q-1];
if (P[q] == T[i])
{
q++;
}
if (q == m)
{
printf("Pattern occurs with shift:%d\n",(i-m+1));
}
}
}
next數(shù)組詳解
舉個例子
kmpnext數(shù)組舉例子.png
