O(模式串数量 x 模式串长度)
O(节点个数 x 树高)
O( 主串长度 x 树高)
, 如果模式串长度不是很长, 则字典树很扁,则AC自动机的搜索过程复杂度趋近于O(n)he、she、hers、his、shy
等字符串树的BFS遍历伪代码:
queue = Queue()
queue.put(self.root) # 先把根节点入队
# 只要队列不为空, 就每次取出队头节点, 然后将该节点的所有子节点依次入队, 依次循环完成BFS遍历
while not queue.empty():
# 取出队头消费
parentNode = queue.get()
.....
# 获取所有将该节点所有子节点依次入队
for childrenNode in parentNode.getAllChildrenNode():
queue.put(childrenNode)
1、AC字典树节点设计:
class Node:
def __init__(self) -> None:
# 失败指针
self.fail: Node = None
# 哈希表存放所有子节点, key是字符, value是对应的Node节点
self.next: Dict[str, Node] = {}
# 标记单词结尾: 如果该节点是单词结尾, 用set集合存放其单词长度
self.wordLenSet = set()
2、将一个单词插入字典树:
def insert(self, pattern):
# 从根节点开始, 从cur指针遍历字典树
cur = self.root
# 遍历每一个字符
for c in pattern:
# 如果该节点的孩子节点中不存在该字符, 则新建并插入
if not cur.next.get(c):
cur.next[c] = Node()
# 指向下一个字符节点
cur = cur.next.get(c)
# 最后cur指向最后一个字符节点, 将其标记为单词结尾
cur.wordLenSet.add(len(pattern))
比如将模式串 he、she、hers、his、shy
依次插入字典树后, 并构建成AC字典树如下
什么失败指针
节点A的fail指针指向节点B
, 那么节点B的代表的单词是节点A代表的单词的最长后缀假设下图是构建好的失败指针的字典树:
失败指针有什么用?
AC自动机构建失败指针过程动画演示:
代码实现
pFail=pFail.fail
, 从pFail的失败指针开始继续寻找, 以此循环回退. def buildFial(self):
queue = Queue()
queue.put(self.root)
# 对字典树进行BFS遍历对每个节点的所有孩子节点构建失败指针
while not queue.empty():
parentNode: Node = queue.get()
# 对每个孩子节点构建失败指针
for c, node in parentNode.next.items():
# 孩子节点node的父节点的失败指针
pFail = parentNode.fail
# 循环判断其父节点的失败指针下是否存在该字符,如果有指向它并退出, 否则最终回退到指向根节点
while pFail is not None and not pFail.next.get(c):
pFail = pFail.fail
# 如果pFail为null说明回退到了根节点说明在树上不存在最长后缀,直接指向root
if pFail is None:
node.fail = self.root
else:
node.fail = pFail.next.get(c)
# 把失败指针存放的单词长度也添加进来这个失配的节点,方便后面快速获取到所有匹配的模式串
if len(node.fail.wordLenSet) > 0:
node.wordLenSet.update(node.fail.wordLenSet)
#
queue.put(node)
i - wordLen + 1
计算得到每个模式串在主串索引的起始位置index, 所以[index, index + wordLen]
就是其在主串的索引范围比如对主串 ishery
进行搜索匹配找出的所有的模式串过程
代码实现
# 搜索主串, 找出其中所有包含的模式串
def search(self, text):
cur = self.root
for i in range(len(text)):
# 如果该节点不存在该字符, 则从失败指针继续判断, 不断回退直到找到或者回退到根节点
while cur.fail and cur.next.get(text[i]) is None:
cur = cur.fail
if cur.next.get(text[i]):
cur = cur.next.get(text[i])
# 如果匹配成功并且该节点是单词结尾, 用 i - 单词长度即可获得模式串在主串的位置
if len(cur.wordLenSet) > 0:
for wordLen in cur.wordLenSet:
index = i - wordLen + 1
match = text[index:i+1]
print(f"匹配到了模式串: {match}, 其实索引为: {index}")
from queue import Queue
from typing import Dict
class Node:
def __init__(self) -> None:
# 失败指针
self.fail: Node = None
# 哈希表存放所有子节点, key是字符, value是对应的Node节点
self.next: Dict[str, Node] = {}
# 如果该节点是单词结尾, 用set结合存放其单词长度
self.wordLenSet = set()
class AcTree:
def __init__(self, patternList) -> None:
self.root = Node()
# 将所有单词插入字典树
for e in patternList:
self.insert(e)
# 对字典树构建失败指针
self.buildFial()
def insert(self, pattern):
# 从根节点开始, 从cur指针遍历字典树
cur = self.root
# 遍历每一个字符
for c in pattern:
# 如果该节点的孩子节点中不存在该字符, 则新建并插入
if not cur.next.get(c):
cur.next[c] = Node()
# 指向下一个字符节点
cur = cur.next.get(c)
# 最后cur指向最后一个字符节点, 将其标记为单词结尾
cur.wordLenSet.add(len(pattern))
def buildFial(self):
queue = Queue()
queue.put(self.root)
# 对字典树进行BFS遍历对每个节点的所有孩子节点构建失败指针
while not queue.empty():
parentNode: Node = queue.get()
# 对每个孩子节点构建失败指针
for c, node in parentNode.next.items():
# 孩子节点node的父节点的失败指针
pFail = parentNode.fail
# 循环判断其父节点的失败指针下是否存在该字符,如果有指向它并退出, 否则最终回退到指向根节点
while pFail is not None and not pFail.next.get(c):
pFail = pFail.fail
# 如果pFail为null说明回退到了根节点说明在树上不存在最长后缀,直接指向root
if pFail is None:
node.fail = self.root
else:
node.fail = pFail.next.get(c)
# 把失败指针存放的单词长度也添加进来这个失配的节点,方便后面快速获取到所有匹配的模式串
if len(node.fail.wordLenSet) > 0:
node.wordLenSet.update(node.fail.wordLenSet)
#
queue.put(node)
# 搜索主串, 找出其中所有包含的模式串
def search(self, text):
cur = self.root
for i in range(len(text)):
# 如果该节点不存在该字符, 则从失败指针继续判断, 不断回退直到找到或者回退到根节点
while cur.fail and cur.next.get(text[i]) is None:
cur = cur.fail
if cur.next.get(text[i]):
cur = cur.next.get(text[i])
# 如果匹配成功并且该节点是单词结尾, 用 i - 单词长度即可获得模式串在主串的位置
if len(cur.wordLenSet) > 0:
for wordLen in cur.wordLenSet:
index = i - wordLen + 1
match = text[index:i+1]
print(f"匹配到了模式串: {match}, 其实索引为: {index}")
if __name__ == '__main__':
# 测试
ac = AcTree(["he", "she", "hers", "his", "shy"])
ac.search("ishery")
console.log ,作为一个前端开发者,可能每天都会用它来分析调试,但这个简单函...
简介 “ 大家好我是帅哥欢迎来到帅哥的程序人生我会把经历分享出来助你了解圈内...
不少Windows 10用户之前都抱怨一个问题,那就是系统的屏幕出现了渲染问题,而微...
一、Postman背景介绍 用户在开发或者调试网络程序或者是网页B/S模式的程序的时候...
本文转载自微信公众号「Linux开发那些事儿」,作者 LinuxThings 。转载本文请联...
互联网业务往往使用MySQL数据库作为后台存储,存储引擎使用InnoDB。我们针对互联...
继 Australis 和 Photon 之后,Mozilla 现又酝酿为 Firefox 带来名为Proton的全...
开发过程中,我们经常会遇到代码回滚的情况。正常人都知道,git 回滚有两大宝: ...
前言 aop即是面向切面编程,众多Aop框架里Castle是最为人所知的,另外还有死去的...
2月26日消息 众所周知,Windows 10 的安全更新和其他重要累计更新通常是在同一天...