改进AC算法用于多模式匹配和检测非连续子序列
一、背景
AC算法进行多模式匹配的原理文章是1975年的Efficient string matching: an aid to bibliographic search一文。
对该算法进行比较好解释的网络文章是:https://blog.csdn.net/lemon_tree12138/article/details/49335051
但是,该算法无法完成非连续子序列的多模式匹配查找。
AC算法的优势是降低计算复杂度,对目标序列进行一次扫描,即可查找所有匹配到的模式。
二、我的改进算法:
以字符串“uhiteeceh”为例,设定需要匹配的模式串为“it/hit/ice/itch”,传统的AC算法构造的自动机如下图所示。具体过程可以见前述背景中的论文和网文。由于检测的是连续子序列,可以在“uhiteeceh”中检测到两种模式“it/hit”。而对于另外两种模式“ice/itch”,则无法查找。
为了检测非连续子序列,我提出了改进算法。保留AC算法的Success表,去除AC算法的Failure表。算法流程图如下:
仍以字符串“uhiteeceh”为例,设定需要匹配的模式串为“it/hit/ice/itch”,但是查找非连续子序列,过程如下:
相关推荐
qidu 2020-07-05
JnX 2020-06-27
lancanfei 2020-06-14
Justdoit00 2020-06-08
山水沐光 2020-05-25
lovejfh 2020-05-14
muhongdi 2020-05-12
yuanran0 2020-05-11
shawsun 2020-05-10
qidu 2020-03-04
Buerzhu 2020-01-21
xhao 2020-01-11
eroshn 2019-11-09
yishujixiaoxiao 2019-11-05
RuoShangM 2019-10-23
TheBigBlue 2019-10-21