当前位置:首页 >> 学科竞赛 >>

广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 04串教案


§4
§4.1 串的匹配



子串的定位操作称为串的模式匹配,是各种串处理中最重要的操作。在主字符串 S 中 查找模式字符串 P,若在主串中找到等于模式串的子串,称为匹配成功,返回与模式串第 一个相等的字符在主串中的序号;若匹配不成功,则返回 0。 §4.1.1 串的简单匹配 串的简单匹配,基本思想是:从主串的第一个字符起和模

式串的第一个字符比较,若 相等,则继续逐个比较后续的字符,否则从主串的第二个字符起再重新和模式串的字符比 较。依此类推,直至模式串的每个字符依次和主串中的一个连续的字符序列相等,则为匹 配成功?? 【例 4-1-1】 : 主串:a b a b c a b c a c b a b 匹配串:a b c a c ↓i =3 第一趟匹配: a b a b c a b c a c b a b a b c ↑j =3 ↓i=2 第二趟匹配: a b a b c a b c a c b a b a ↑j=1 ↓i=7 第三趟匹配: a b a b c a b c a c b a b a b c a c ↑j=5 ↓i=4 第四趟匹配: a b a b c a b c a c b a b a ↑j=1 ↓i=5 第五趟匹配: a b a b c a b c a c b a b a ↑j=1 ↓i=11 第六趟匹配: a b a b c a b c a c b a b a b c a c ↑j=6 这种算法易于理解, 在某些场合效率也较高。 但当主串为 ‘0000000000000000000000000 00000000000000000000000001’ ,模式串为‘00000001’时,由于模式串中前 7 各字符均为 ‘0’ ,主串中前 50 各字符均为‘0’ ,每趟比较都在模式串的最后一个字符出现不等,此时 需将指针 i 回溯到 i-6 的位置上,并从模式的第一个字符开始重新比较。直到匹配成功, 指针 i 需回溯 43 次。这经常出现在主串中存在多个子串和模式串“部分匹配”的情况下, 例如 01 串(字符串由 0、1 组成) 。

§4.1.2 串的 KMP 匹配算法 这种改进的算法是由 D.E.Knuth、V.R.Pratt 和 J.H.Morris 三人同时发现的,所以称 为 KMP 算法。 (一)KMP 算法的基本思路 KMP 算法每当一趟匹配过程中发现字符不等时,不需回溯 i 指针,而是利用已经得到 的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后,继续进行比较。 先回顾简单匹配的算法,从例 4-1-1 可以看出,在第三趟匹配中,当 i=7、j=5 字符比 较不等时,又从 i=4、j=1 重新比较。而在 i=4 和 j=1,i=5 和 j=1,以及 i=6 和 j=1 这三 次比较都是不必要的。 因为从第三趟部分匹配的结果可以看出,主串中第 4、5、6 个字符必然 是’b’、’c’、’a’(即模式串中第 2、3、4 个字符) 。因为模式串中第一个字符是 a, 因为它无需和这三个字符进行比较, 所以仅需将模式串向右滑动三个字符的位置进行比较。 同理,在第一趟匹配中出现字符不等时,仅需将模式串向右移动 2 个字符的位置继续进行 i=3、j=1 时的字符比较。由此,整个过程指针 i 没有回溯,如下所示。 ↓i=3 第一趟匹配:a b a b c a b c a c b a b a b c ↑j=3 ↓i=7 第二趟匹配:a b a b c a b c a c b a b a b c a c ↑j=5 ↓i=11 第三趟匹配:a b a b c a b c a c b a b a b c a c ↑j=6 KMP 算法的基本思想是: 在匹配过程中,当 Si≠Pj 时, 应在模式串 P 的开头和主串 S 紧靠 i 之前找到相等的最 大子串,子串长度为 k –1,如图所示: i S P k-1 k j

然后将模式串向右滑动,比较 Si 和 Pk 是否相等。 对于 KMP 算法,需要解决的问题首先是:当匹配过程产生“失配” ,模式串“向右滑动” 可行多远?换句话说, 当主串中第 i 个字符与模式串中第 j 个字符 “失配” (即不相等) 时, 主串中第 i 个字符应与模式串中哪个字符再比较?

(二)求证 k 仅与模式串相关 设主串为 S, 模式串为 P。 假设当主串中第 i 个字符与模式串中第 j 个字符 “失配” 时, 主串的第 i 个字符应与模式串的第 k 个字符继续比较,则模式串中前 j 个字符必须满足下 列关系: ‘P1P2??Pk-1’=‘Si - k+1Si - k+2??Si-1’ (1)

{匹配串 P 的前 k-1 个字符与主串中第 i 个字符前的 k-1 个字符相等} 而已经得到“部分匹配”的结果是: ‘Pj-k+1Pj-k+2??Pj-1’=‘Si-k+1Si-k+2??Si-1’ (2)

{匹配串 P 第 j 个字符前的 k-1 个字符与主串中第 i 个字符前的 k-1 个字符相等} 由(1)和(2) ,可以推出下式: ‘P1P2??Pk-1’=‘Pj-k+1Pj-k+2??Pj-1’ 即模式串中前 k-1 个字符与第 j-k+1 到 j-1 个字符相等,即 k 仅与模式串有关,与主 . 串无关 。 ... (三)next 数组 因此,我们可以设 next 数组,令 next[j]=k,则 next[j]表明当模式中第 j 个字符与 主串相应字符“失配”时,主串中该字符重新与模式串中进行比较的字符的位置。 Next 数组的定义: next[j]= 空时 1 【例 4.1.2_1】 j 模式串 next [ j ] 1 2 3 4 5 6 7 8 a b a a b c a c 0 1 1 2 2 3 1 2 其它情况 0 当 j=1 时 Max { k | 1<k<j 且 ‘p1??pk-1’=‘pj-k+1??pj-1’ } 当此集合不

Next 数组怎样具体求得,我们这里先放一下,先看看在设了 next 数组后 KMP 匹配的 算法,这可能将更有利于理解。 (四)KMP 算法 匹配可如下进行: ① 指针 i 和 j 分别指示主串和模式串中正待比较的字符,令 i 和 j 的初值皆为 1。 ② 若在匹配过程中 si = pi ,则 i 和 j 分别增 1,否则 j 再退到下一个 next 值的位置, 依此类推,直至下列可能:

一种是 j 退到某个 next(next [next [? next[ j ] ] ])值时字符比较相等, 则指针各自增 1 继续进行匹配(模式串滑动) ; 另一种是 j 退到 next 值为 0(即模式的第一个字符“失配” ) ,则此时需将模式 串继续向右滑动一个位置,从主串的下一个字符 si+1 起和模式串重新开始匹配。 算法如下: function KMP:integer; ?? {假设已求出 next 数组} begin i:=1; j:=1; {指针初始化} while (i<=s.length) and (j<=p.length) do {s.length、p.length 分别为主串和模 式串的长度} if (j = 0) or (s[i]=p[i]) then begin i:=i+1; j:=j+1; {继续下一对字符的比较} end else j:=next[j]; {模式串向右滑动} if j>p.length then KMP:=i-p.length {匹配成功} else KMP:=0; end; (五)求 next 数组的算法 从上述讨论已知,next 数组的值仅与模式串本身有关,而与相匹配的主 串无关,我 们可以根据模式串,从分析其定义出发,用递推的方法求得 next 数组的值。 由定义知: next [1] = 0

设已求得 next [ j ] = k ,求 next [ j+1 ] = ? 有两种情况: 1.若 Pk = Pj ,则表明在模式串中: ‘P1??Pk’=‘Pj - k+1??Pj’ 就是说 next [ j+1 ] = k+1 , 即:next [ j+1 ] = next [ j ] +1 2.若 Pk≠Pj,则表明在模式串中: ‘P1??Pk’≠‘Pj – k+1??Pj’ 此时如何处理? procedure next; var i , j , k :integer; begin next [1] := 0; k := 0; for j := 1 to p_length -1 do begin

{ p_length 为模式串 P 的长度}

if (k = 0) or (P[j] = P[k]) then begin

end else begin

end; end; end; 参考答案:① k := k+1; next [j+1] := k; ② repeat k := next [k]; until(k=0)or(P[j]=P[k]) ; k := k+1; next [j+1] := k; 求 next 数组程序 2: procedure next; var j , k :integer; begin j := 1; k := 0; next[1] := 0; while j < p_length do if(k=0)or(P[j]=P[k]) then begin j := j+1; k := k+1; next[j] := k; end else k := next[k]; end; 另一种求 next 数组的算法: procedure next; readln (p);

next[1]:= 0; for j:=2 to p_length do begin k := j-1; repeat k:=k-1; until copy(p,1,k) = copy(p,j-k,k); next[j] := k+1; end; end;

(六)进一步优化: 前面定义的 next 函数在某些情况下尚有缺陷,例如: 模式串 P=‘aaaab’和主串 S=‘aaabaaaab’匹配 当 i=4,j=4,S[4]≠P[4]时,由 next[j]的指示,模式串向右移,S[4]还要与 P[3]、 P[2]、P[1]继续比较。实际上,因为模式串中第 1、2、3 个字符和第 4 个字符都相等,没 必要再和 S[4]相比较,可将模式串直接向右滑动 4 个字符,进行 i=5、j=1 时的比较。 为了克服这种不必要的重复比较,对求 next 的算法进行改进,其基本思想是:在求得 j 点的 k 值后,在判断 P[k]和 P[j]是否相等,若相等则把 nextval[k]值送 nextval[j]中, 否则把原来的 k 值存入 nextval[j]中。表中的 nextval[j]就是改进后的值。 j 模式串 P next[j] nextval[j] 1 a 0 0 2 3 4 5 6 7 8 9 10 11 b c a b c a b b 1 1 1 2 3 4 5 6 1 1 0 1 1 0 1 6 a c 1 2 0 2

算法为: procedure next2; var j,k :integer; begin j:= 1; k := 0; nextval[1] := 0; while j<p_length do if (k=0)or(P[j]=P[k]) then begin j := j+1; k := k+1; if P[j]=P[k] then nextval[j] := nextval[k] else nextval[j] := k;

end else k := nextval[k]; end;

§4.1.3 串的 BM 匹配算法 在实际的模式匹配中,往往失配的机会反而比匹配的机会要多,针对这种情况, BM (Boyer-Moore)采取从模式串末端往前匹配的算法,简称 BM 算法。 实现这个算法首先是求出模式串的 nextb 数组值,然后进行模式匹配。 (1)求 nextb 数组值 基本思想:把模式串中每个字符(称 ch)至模式串最末尾字符的距离(若模式串中有 相同的字符, 只记下离尾端最近的那个字符的距离) 分别存放到每个字符所对应的 nextb[ch] 中,不在模式串中出现的字符,其 nextb[ch]值为模式串长 m。 nextb[ch] = 或 nextb[ord(ch)] m m - max{ j | 1≤j≤m-1 且 pj=ch }

为讨论的简单起见,设串都是小写字母,例如有模式串 P=‘abcdcfd’,长度 m=7, 其 nextb 数组中值如表所示。其中 nextb[‘g’]至 nextb[‘z’]的值均为 7。 ch nextb[ch] a 6 b 5 c 2 d 3 e 7 f 1 g 7 h 7 ?? ?? z 7

算法: type car = array [ ‘a’ .. ‘z’ ] of integer; ?? procedure nextb(p:string;var nextb:car) ; var i : char; j , m : integer; begin m := p_length; for i := ‘a’ to ‘z’ do nextb[ i ] := m; for j := 1 to m-1 do nextb[p[j]] := m-j; end; (2)BM 匹配算法 基本思想:从模式串 P 尾端字符和主串 S 相对应位字符开始比较,若相等则继续往前 (向左)逐个比较,否则将串 P 右移 nextb[ch]位(此处 ch 是模式串 P 尾端字符相对应主 串 S 中的相应字符) ,然后从 P 的尾端字符和 S 中相对应的字符重新开始比较,若相等则继 续往前比,依此类推,直至最后匹配成功或失败为止。 【例】 7 14 ↓ ↓ S:a y t u k l m a b o p w a c n e a b c d c f d h s ╫

P:a b c d c f d P 右移 7 位后: P 右移 2 位后: ╫ a b c d c f d ╫ a b c d c f d

P 右移 7 位后: a b c d c f d h s 算法如下: function BM_match(s , p : string; nextb : car): integer; var i , j , k , m , n : integer; begin m := p_length; n := s_length; i := m; repeat j := m; k := i; while(j>0)and(s[k] = p[j])do begin j := j – 1; k := k – 1; end; if j<>0 then i := i + nextb[ s[i] ]; until (j = 0)or(j > n) ; if j = 0 then BM_match := i – m + 1 else BM_match := 0; end; §4.1.3 串的广义匹配 设主串 S 和模式串 P,按模式串中字符顺序在主串中顺序找到但不一定连续与模式串 相同的字符序列,称之为广义匹配。广义匹配具有许多的用途,如数据库的模糊查询等。 例如: 主串 S=‘ a c d a c b e m’ 模式串 P=‘d c b’ S: a c d a c b e m P: d c b

显然有 S3S5S6=P1P2P3 参考算法如下,它主要适用于 ASCII 码字符和汉字字符。 program gypp; var p , s : string; i , j , k : integer; d : array [1 . . 260] of integer; Begin write (' P: '); readln (p); write (' S: '); readln (S); i := 1; j := 0; while i<=length(s) do if p[j+1]=s[i] then begin j := j+1;

begin

d[j] := i; i := i+1; end else i := i+1; end;

if j=0 then writeln ('No find') else for k:=1 to j do write (d[k]:3); End.

【综合练习】 1、 求回文数 若一个数(首位不为零)从左向右读与从右向左读都是一样,则称为回文数。有一种 求回文数的方法: 例如,给定一个十进制整数 56,将 56 加 65(即把 56 从右向左读) ,得到的 121 是一 个回文数;又如,对于十进制数 87,按以上方法用 4 步可以得到回文数 4884。 step1: 87+78=165 step3: 726+627=1353 step2:=165+561=726 step4:=1353+3531=4884

给定一个 N 进制数 m, (2<=N<=16, m 的位数上限为 20) ,求最少经过几步可以得到回 文数。如果在 30 步以内不能得到回文数,则输出“impossible”。 输入:只有 2 个整数 N 和 m 。 输出:步数/impossible 输入样例: 9 87

输出样例: 6

2、 构造字串 生成长度为 n 的字串,其字符从 26 个大写英文字母的前 p 个字母中选取,使得没有相 邻的子序列相等。 例如: p=3 , n=5 时: ‘ABCBA’满足条件, ‘ABCBC’不满足条件。 输入: n p 输出:满足条件的字串


相关文章:
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 04串教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 04串教案_学科竞赛_高中教育_教育专区。§4 §4.1 串的匹配 串 子串的定位操作称为串的模式匹配,...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 08图教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 08图教案_学科竞赛_高中教育_教育专区。§8 §8.1 图的基本概念 图 图: 图是数据结构 G=(V,...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 01数据结构概论教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 01数据结构概论教案_学科竞赛_高中教育_教育专区。§1 §1.1 什么是数据结构 概论 数据结构(Data ...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案_学科竞赛_高中教育_教育专区。§5 §5.1 特殊矩阵 §5.1.1 三角矩阵与...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 02线性表教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 02线性表教案_学科竞赛_高中教育_教育专区。§2 §2.1 线性表的定义及其基本运算 线性表 线性表是...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案_学科竞赛_高中教育_教育专区。§3 §3.1 栈 栈和队列 栈(stack)是一种仅限于在...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 06广义表教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 06广义表教案_学科竞赛_高中教育_教育专区。§6 §6.1 广义表的定义 广义表 广义表 (Lists) 又称...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 07树教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 07树教案_其它课程_高中教育_教育专区。§7 §7.1 树的概念 树 【定义】 树(Tree)是 n(n>0...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 09内部排序教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 09内部排序教案_学科竞赛_高中教育_教育专区。§9 内部排序 在《数据结构》里,排序一般分为:插入...
信息技术竞赛培训教程_数据结构
数据结构数据结构隐藏>> 信息技术竞赛培训教程目录 第二部分 数据结构 (一)――栈 (二)――队列 (三)――链表 (四)――迭代与递推 (五)――递归 (六)―...
更多相关标签:
广东省汕头市金山中学 | 广东省汕头市潮阳区 | 广东省汕头市 | 广东省汕头市潮南区 | 广东省汕头市邮编 | 广东省汕头市澄海区 | 广东省汕头市金平区 | 广东省汕头市地图 |