|
|
本帖最后由 51hei社區(qū) 于 2016-1-16 06:58 編輯
前提條件:
S代表主串,
P代表模式串
下標(biāo)從0開(kāi)始
引入:下面兩個(gè)字符串,判斷P是否是S的子串
S: a b a b a b c a b c a c b ab
P: a b c
最普通的算法就是拿S和P一個(gè)一個(gè)比較,如果發(fā)現(xiàn)某一次匹配失敗,則S從第一個(gè)P從頭,再次進(jìn)行比較.直到全部匹配結(jié)束.
缺點(diǎn):復(fù)雜度最壞O(n*m),同時(shí)下標(biāo)回溯發(fā)生在S和P中.
KMP算法:如果概念很熟悉.請(qǐng)直接跳過(guò)~~~
如果某一次匹配失敗,那么回溯多少合適呢?
比如:
S : ababcabc
P: ababcaba
現(xiàn)在最后一個(gè)字符匹配失敗.
我們來(lái)分析下最簡(jiǎn)單的模式匹配過(guò)程:S回溯到下標(biāo)1.P從頭開(kāi)始,如下
ababcabc
ababcaba
繼續(xù)匹配,第一次即失敗. S回溯到下標(biāo)2.P從頭開(kāi)始,如下
ababcabc
ababcaba
繼續(xù)匹配,第三次即失敗. S回溯到下標(biāo)3.P從頭開(kāi)始,如下
ababcabc
ababcaba
繼續(xù)匹配,第一次即失敗. S回溯到下標(biāo)4.P從頭開(kāi)始,如下
ababcabc
ababcaba
繼續(xù)匹配,第一次即失敗. S回溯到下標(biāo)5.P從頭開(kāi)始,如下
ababcabc
ababcaba
繼續(xù)匹配…結(jié)果到了c碰到第二次匹配失敗…
注意第一次c是匹配到P的最后一個(gè)字符失敗,第二次是匹配到P的第三個(gè)字符失敗.
再這兩次的過(guò)程中.做了很多工作..
我們發(fā)現(xiàn)是不是可以再這方面優(yōu)化呢
我們發(fā)現(xiàn)無(wú)論S怎么進(jìn)行回溯,其下標(biāo)最后判斷總是可以再c這個(gè)上面.
還有P回溯時(shí),其實(shí)只要直接做
ababcabc
ababcaba
這一次就好了.
接著上面的問(wèn)題,也就是說(shuō)回溯多少合適呢?再這里P回溯2比較合適
證明:S0,S1,………………………………Si-1,Si
P0,P1,………………………………Pj-1,Pj
假設(shè)在Si和Pj中發(fā)生的匹配失敗.那我們肯定知道
S0,S1,………………………………Si-1
P0,P1,………………………………Pj-1
是相等的.
假設(shè)我們P回溯到下標(biāo)k比較合適,也就是說(shuō)下一次比較是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因?yàn)镾0,…Si-1 和P0,…Pj-1是相等的,且j是大于k的值
所以P0,P1,…………Pk-1 =Pj-k, …………Pj-1
所以看出.S不用回溯.回溯只跟P有關(guān).
我們既然每次都可以回溯一個(gè)比較合理的值,那算法就非常好寫(xiě)了.
關(guān)鍵就是這個(gè)k如何去尋找...這個(gè)下回再說(shuō).
--------------------------------------------------
上回說(shuō)到.要確保P0,P1,…………Pk-1 = Pj-k, …………Pj-1這個(gè)表達(dá)式成立
則需要找到里面的k值,next有以下定義:
既然是推導(dǎo),肯定要設(shè)定一些條件.我們假設(shè)
已有next[j] = k ,求next[j+1] = ?
既然已有next[j] = k,那么肯定有.P0,P1,…………Pk-1 = Pj-k,…………Pj-1,但我們對(duì)于Pk 和 Pj的關(guān)系不清楚,讓我們分開(kāi)討論
如果此時(shí)Pk = Pj
那么肯定有 P0,P1,…………Pk-1 = Pj-k, …………Pj-1,Pj明顯看到左右的長(zhǎng)度都加了1.也就是說(shuō)在原來(lái)的基礎(chǔ)上長(zhǎng)度加了1.
則 next[j+1] = next[j] + 1 = k + 1;
如果此時(shí)Pk ≠ Pj
這地方很繞...最起碼我學(xué)習(xí)的時(shí)候是...請(qǐng)?jiān)敿?xì)看,我也盡量分析的詳細(xì)點(diǎn).
說(shuō)明不會(huì)含有[0,k]長(zhǎng)度的字符串與[k+1,j-1]
雖然這個(gè)不相等,但有可能比k小的前綴是相等的.但到底Pj 和前面的哪個(gè)字符串相等呢?
這是不是又牽扯到一個(gè)模式匹配的問(wèn)題捏? 答案是的.
把模式串的后面部分看作新的主串 Pj-k, …………Pj-1,Pj
模式串前面部分看作新的模式串 P0,P1,…………Pk-1,Pk 去尋找新的匹配k'
這時(shí)候的步驟是:
1:出現(xiàn)了Pj和Pk不同.這時(shí)候根據(jù)KMP算法,需要回溯P產(chǎn)生k'.其實(shí)就是移動(dòng)next(k).
2:由于帶入后末尾2個(gè)匹配就是一樣的了.Pk' = Pj所以就可以得出,從j+1的字符之前存在一個(gè)長(zhǎng)度為k'的最長(zhǎng)字串
P0……..Pk' = Pj-k’……Pj.也就是說(shuō)next[j+1] = k’+1
next[j+1] = next(k) + 1;
舉個(gè)例子吧.
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
|
現(xiàn)在求next(10)?
分解成next(9+1) ,已知next(9) = 4 ,判斷P4 == P9?
因?yàn)镻4=c P9=a 所以不相等next(9+1) = next(4) + 1 = 3 請(qǐng)自己驗(yàn)證.
下面用白話解釋上面的公式下,看next(9) = 4,那從9往前看4個(gè) 是abab....肯定第一個(gè)到第四個(gè)也是abab
假設(shè)如果next(10) = 5 如果從10往前面看ababa 第一個(gè)到第五個(gè)肯定也是ababa這個(gè)是肯定的.但實(shí)際上第一個(gè)到第五個(gè)是ababc
但p[19] = a ...發(fā)現(xiàn)了吧是拿a和c比的.結(jié)果發(fā)現(xiàn)不同..
說(shuō)明[0,k]長(zhǎng)度的字符串與[k+1,j-1]是不會(huì)相同的.只有從[0,k]中找一個(gè)k'來(lái)進(jìn)行小范圍的匹配的...這個(gè)東西明顯就是next[k]...
希望我說(shuō)明白了.哈哈
再來(lái)一個(gè)吧next(6)?
分解成next(5+1) ,已知next(5) = 0 ,判斷P5 == P0?
因?yàn)镻5=a P0=a 所以相等next(5+1) = next(5) + 1 = 1 請(qǐng)自己驗(yàn)證.
其實(shí)next算法還有能可以優(yōu)化的...因?yàn)橛幸环N極端的情況.下回說(shuō)~
-------------------------------------------
還有一種特殊情況需要考慮:
例如:
aaabaaabaaabaaabaaab
aaaab
使用上次我們說(shuō)的算法計(jì)算出next
next[j] = -10123
下面進(jìn)行匹配過(guò)程:
s[3] = b ,p[3] = a 不匹配,P回溯到next[3].發(fā)現(xiàn)還是a,再回溯還是a再回溯....
其實(shí)a和a是相同的,我們應(yīng)該有個(gè)策略告訴他,不需要再重復(fù)比較了.
于是
本來(lái)sj 不等于 pi的 那么要sj和pk相比. 而k=next[ i]的
此時(shí)如果pi=pk的話,那么sj肯定也不等于pk,所以就不用比了.
這時(shí)候回溯多少可以與next[next[ i]]相同....
修正后
next[j] = –1 -1 -1 -1 3
KMP算法告一段落~有時(shí)間把算法貼上來(lái)~
附代碼: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空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
