本帖最后由 51hei社區 于 2016-1-16 06:58 編輯
前提條件:
S代表主串,
P代表模式串
下標從0開始
引入:下面兩個字符串,判斷P是否是S的子串
S: a b a b a b c a b c a c b ab
P: a b c
最普通的算法就是拿S和P一個一個比較,如果發現某一次匹配失敗,則S從第一個P從頭,再次進行比較.直到全部匹配結束.
缺點:復雜度最壞O(n*m),同時下標回溯發生在S和P中.
KMP算法:如果概念很熟悉.請直接跳過~~~
如果某一次匹配失敗,那么回溯多少合適呢?
比如:
S : ababcabc
P: ababcaba
現在最后一個字符匹配失敗.
我們來分析下最簡單的模式匹配過程:S回溯到下標1.P從頭開始,如下
ababcabc
ababcaba
繼續匹配,第一次即失敗. S回溯到下標2.P從頭開始,如下
ababcabc
ababcaba
繼續匹配,第三次即失敗. S回溯到下標3.P從頭開始,如下
ababcabc
ababcaba
繼續匹配,第一次即失敗. S回溯到下標4.P從頭開始,如下
ababcabc
ababcaba
繼續匹配,第一次即失敗. S回溯到下標5.P從頭開始,如下
ababcabc
ababcaba
繼續匹配…結果到了c碰到第二次匹配失敗…
注意第一次c是匹配到P的最后一個字符失敗,第二次是匹配到P的第三個字符失敗.
再這兩次的過程中.做了很多工作..
我們發現是不是可以再這方面優化呢
我們發現無論S怎么進行回溯,其下標最后判斷總是可以再c這個上面.
還有P回溯時,其實只要直接做
ababcabc
ababcaba
這一次就好了.
接著上面的問題,也就是說回溯多少合適呢?再這里P回溯2比較合適
證明:S0,S1,………………………………Si-1,Si
P0,P1,………………………………Pj-1,Pj
假設在Si和Pj中發生的匹配失敗.那我們肯定知道
S0,S1,………………………………Si-1
P0,P1,………………………………Pj-1
是相等的.
假設我們P回溯到下標k比較合適,也就是說下一次比較是Si和Pk.
那么肯定有
S0,S1,………………………………Si-1,Si
P0,P1,………………………………Pj-1,Pj
P0,P1,…………Pk-1,Pk
P0,P1,…………Pk-1 =Si-k…………Si-1因為S0,…Si-1 和P0,…Pj-1是相等的,且j是大于k的值
所以P0,P1,…………Pk-1 =Pj-k, …………Pj-1
所以看出.S不用回溯.回溯只跟P有關.
我們既然每次都可以回溯一個比較合理的值,那算法就非常好寫了.
關鍵就是這個k如何去尋找...這個下回再說.
--------------------------------------------------
上回說到.要確保P0,P1,…………Pk-1 = Pj-k, …………Pj-1這個表達式成立
則需要找到里面的k值,next有以下定義:
既然是推導,肯定要設定一些條件.我們假設
已有next[j] = k ,求next[j+1] = ?
既然已有next[j] = k,那么肯定有.P0,P1,…………Pk-1 = Pj-k,…………Pj-1,但我們對于Pk 和 Pj的關系不清楚,讓我們分開討論
如果此時Pk = Pj
那么肯定有 P0,P1,…………Pk-1 = Pj-k, …………Pj-1,Pj明顯看到左右的長度都加了1.也就是說在原來的基礎上長度加了1.
則 next[j+1] = next[j] + 1 = k + 1;
如果此時Pk ≠ Pj
這地方很繞...最起碼我學習的時候是...請詳細看,我也盡量分析的詳細點.
說明不會含有[0,k]長度的字符串與[k+1,j-1]
雖然這個不相等,但有可能比k小的前綴是相等的.但到底Pj 和前面的哪個字符串相等呢?
這是不是又牽扯到一個模式匹配的問題捏? 答案是的.
把模式串的后面部分看作新的主串 Pj-k, …………Pj-1,Pj
模式串前面部分看作新的模式串 P0,P1,…………Pk-1,Pk 去尋找新的匹配k'
這時候的步驟是:
1:出現了Pj和Pk不同.這時候根據KMP算法,需要回溯P產生k'.其實就是移動next(k).
2:由于帶入后末尾2個匹配就是一樣的了.Pk' = Pj所以就可以得出,從j+1的字符之前存在一個長度為k'的最長字串
P0……..Pk' = Pj-k’……Pj.也就是說next[j+1] = k’+1
next[j+1] = next(k) + 1;
舉個例子吧.
0 1 2 3 4 5 6 7 8 9 10
-1
| 0
| 0
| 1
| 2
| 0
| 1
| 2
| 3
| 4
| ?
| a
| b
| a
| b
| c
| a
| b
| a
| b
| a
| b
|
現在求next(10)?
分解成next(9+1) ,已知next(9) = 4 ,判斷P4 == P9?
因為P4=c P9=a 所以不相等next(9+1) = next(4) + 1 = 3 請自己驗證.
下面用白話解釋上面的公式下,看next(9) = 4,那從9往前看4個 是abab....肯定第一個到第四個也是abab
假設如果next(10) = 5 如果從10往前面看ababa 第一個到第五個肯定也是ababa這個是肯定的.但實際上第一個到第五個是ababc
但p[19] = a ...發現了吧是拿a和c比的.結果發現不同..
說明[0,k]長度的字符串與[k+1,j-1]是不會相同的.只有從[0,k]中找一個k'來進行小范圍的匹配的...這個東西明顯就是next[k]...
希望我說明白了.哈哈
再來一個吧next(6)?
分解成next(5+1) ,已知next(5) = 0 ,判斷P5 == P0?
因為P5=a P0=a 所以相等next(5+1) = next(5) + 1 = 1 請自己驗證.
其實next算法還有能可以優化的...因為有一種極端的情況.下回說~
-------------------------------------------
還有一種特殊情況需要考慮:
例如:
aaabaaabaaabaaabaaab
aaaab
使用上次我們說的算法計算出next
next[j] = -10123
下面進行匹配過程:
s[3] = b ,p[3] = a 不匹配,P回溯到next[3].發現還是a,再回溯還是a再回溯....
其實a和a是相同的,我們應該有個策略告訴他,不需要再重復比較了.
于是
本來sj 不等于 pi的 那么要sj和pk相比. 而k=next[ i]的
此時如果pi=pk的話,那么sj肯定也不等于pk,所以就不用比了.
這時候回溯多少可以與next[next[ i]]相同....
修正后
next[j] = –1 -1 -1 -1 3
KMP算法告一段落~有時間把算法貼上來~
附代碼:VC2005編譯成功
#include<string.h>
template<typenameT>
classPatternMatch
{
public:
virtual~PatternMatch(){}
virtualintmatch(constT* source,intsourcelen,constT* pattern,intpatternlen) = 0;
};
template<typenameT>
classKmp:publicPatternMatch<T>
{
public:
virtualintmatch(constT* source,intsourcelen,constT* pattern,intpatternlen)
{
intres = -1;
if (!source || sourcelen<=0|| !pattern ||patternlen<=0)
{
returnres;
}
int* next = newint[patternlen];
if (!next)
{
returnres;
}
do
{
if (generate_next(pattern,patternlen,next)<0)
{
break;
}
inti = 0;
intj = 0;
while(i<sourcelen&&j<patternlen)
{
if(-1==j ||source[i]==pattern[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if (j>=patternlen)
{
res =i-patternlen;
}
}while (false);
delete []next;
returnres;
}
protected:
intgenerate_next(constT* pattern,intpatternlen,int* nextarray)
{
if (!pattern || patternlen<=0|| !nextarray)
{
return -1;
}
nextarray[0] = -1;
inti = 0;
intj = -1;
while (i<patternlen-1)
{
if(-1==j ||pattern[i]==pattern[j])
{
++i;
++j;
if (pattern[i]!=pattern[j])
{
nextarray[i] = j;
}
else
{
nextarray[i] = nextarray[j];
}
}
else
{
j = nextarray[j];
}
}
return 1;
}
};
voidmain()
{
Kmp<char>a;
intpos = a.match("abcde",5,"cd",2);
}
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
