改进AC算法用于多模式匹配和检测非连续子序列
2021-05-03 19:29
标签：需要 目标 过程 检测 load inf 完成 论文 查找 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”，但是查找非连续子序列，过程如下： 改进AC算法用于多模式匹配和检测非连续子序列 标签：需要 目标 过程 检测 load inf 完成 论文 查找 原文地址：https://www.cnblogs.com/xiaojieshisilang/p/13197042.html一、背景
二、我的改进算法：
