字符串模式匹配
标签: 数据结构
学习人数: 4394

介绍

模式匹配是数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串,这就是模式匹配。

假设P是给定的子串,T是待查找的字符串,要求从T中找出与P相同的所有子串,这个问题成为模式匹配问题。P称为模式,T称为目标。如果T中存在一个或多个模式为P的子串,就给出该子串在T中的位置,称为匹配成功;否则匹配失败。

 

简单的模式匹配算法 — 蛮力算法 (BF算法)
蛮力算法(Brute-Force),简称BF算法。

算法思想

BF算法的算法思想是:

目标串T的的第一个字符起与模式串P的第一个字符比较。

若相等,则继续对字符进行后续的比较;否则目标串从第二个字符起与模式串的第一个字符重新比较。

直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止,此时称为匹配成功,否则匹配失败。

 

通过下图示例,可一目了然:

算法性能

假设模式串的长度是m,目标串的长度是n。

最坏的情况是每遍比较都在最后出现不等,即没变最多比较m...

登录查看完整内容


课后作业

课后习题

 

【2019年真题】设主串T=“abaabaabcabaabc”,模式串S=“abaabc”,采用KMP算法进行模式匹配,到匹配成功时为止,在匹配过程中进行的单个字符间的比较次数是
A. 9               B. 10                   C. 12                   D. 15

参考答案:B

 

【2015年真题】已知字符串 S 为“abaabaabacacaabaabcc”,模式串 t 为“abaabc”。采用 KMP 算法进行匹配,第一次出现“失配”(s[i]≠t[j]) 时,i=j=5,则下次开始匹配时,i 和j 的值分别是()。
A.i=1,j=0    B.i=5,j=0    C.i=5,j=2    D.i=6,j=2 

参考答案:C


登录后发布评论

暂无评论,来抢沙发