本帖最后由 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空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
