文档介绍：数据结构与算法
-
串的模式匹配
定义在串中寻找子串(第一个字符)在串中的位置
词汇在模式匹配中,子串称为模式,串称为目标。
示例目标 T : “Beijing”
模式 P : “jin”
匹配结果= 3
第1趟 T a b b a b a 穷举的模式
P a b a 匹配过程
第2趟 T a b b a b a
P a b a
第3趟 T a b b a b a
P a b a
第4趟 T a b b a b a
P a b a
int String::Find ( String &pat ) const {
//穷举的模式匹配
char * p = , * s = ch; int i = 0;
if ( *p && *s ) //当两串未检测完
while ( i <= curLen - )
if ( *p++ == *s++ ) //比较串字符 if ( !*p ) return i; //相等
else { i++; s = ch+i; p = ; }
//对应字符不相等,对齐目标的//下一位置,继续比较
return -1;
}
目标 T t0 t1 t2 …… tm-1 … tn-1
模式 pat p0 p1 p2 …… pm-1
目标 T t0 t1 t2 …… tm-1 tm … tn-1
模式 pat p0 p1 …… pm-2 pm-1
目标 T t0 t1 …… ti ti+1…… ti+m-2 ti+m-1… tn-1
‖‖‖‖
模式 pat p0 p1 …… pm-2 pm-1
改进的模式匹配
穷举的模式匹配算法时间代价:
最坏情况比较n-m+1趟,每趟比较m次,
总比较次数达(n-m+1)*m
原因在于每趟重新比较时,目标串的检
测指针要回退。改进的模式匹配算法可
使目标串的检测指针每趟不回退。
改进的模式匹配(KMP)算法的时间代价:
若每趟第一个不匹配,比较n-m+1趟,总比较次数最坏达(n-m)+m = n
若每趟第m个不匹配,总比较次数最坏亦达到 n
T t0 t1 … ts-1 ts ts+1 ts+2 … ts+j-1 ts+j ts+j+1 … tn-1
‖‖‖‖‖
P p0 p1 p2 … pj-1 pj pj+1
则有 ts ts+1 ts+2 … ts+j = p0 p1 p2 …pj (1)
为使模式 P 与目标 T 匹配,必须满足
p0 p1 p2 …pj-1 …pm-1 = ts+1 ts+2 ts+3 … ts+j … ts+m
如果 p0 p1 …pj-1 p1 p2 …pj (2)
则立刻可以断定
p0 p1 …pj-1 ts+1 ts+2 … ts+j
下一趟必不匹配
同样,若 p0 p1 …pj-2 p2 p3 …pj
则再下一趟也不匹配,因为有
p0 p1 …pj-2 ts+2 ts+3 … ts+j
直到对于某一个“k”值,使得
p0 p1 …pk+1 pj-k-1 pj-k …pj
且 p0 p1 …pk = pj-k pj-k+1 …pj
则 p0 p1 …pk = ts+j-k ts+j-k+1 … ts+j
‖‖‖
pj-k pj-k+1 … pj
k 的确定方法
当比较到模式第 j 个字符失配时, k 的值与模式的前 j 个字符有关,与目标无关。
利用失效函数 f (j)可描述。
利用失效函数 f (j) 的匹配处理
如果 j = 0,则目标指针加 1,模式指针回到 p0。
如果 j > 0,则目标指针不变,模式指针回到 pf(j-1)+1。
若设模式 P = p0 p1…pm-2 pm-1
示例:确定失效函数 f (j)