結果

問題 No.430 文字列検索
コンテスト
ユーザー kainade
提出日時 2024-07-25 06:01:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 168 ms / 2,000 ms
コード長 3,242 bytes
コンパイル時間 403 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 89,264 KB
最終ジャッジ日時 2024-11-10 01:11:51
合計ジャッジ時間 2,542 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
NOTE: examples.

# explore
https://atcoder.jp/contests/abc268/submissions/55937468

# fail_tree
https://atcoder.jp/contests/abc362/submissions/55937489

# calc_all_matching_ranges
https://atcoder.jp/contests/abc268/submissions/55937440
"""
from collections import deque
class AhoCorasick:
	class Node:
		def __init__(self, node_id):
			self.id = node_id
			self.trie_par = None
			self.trie_ch = {}
			self.rep_patterns = []
			self.suf_patterns = []

			self.fail_par = None

		def __getitem__(self, i):
			return self.trie_ch[i]
		def __setitem__(self, i, value):
			self.trie_ch[i] = value
			return self
		def __contains__(self, c):
			return c in self.trie_ch

	def __init__(self, patterns, fail_tree=False):
		self.nodes = [self.Node(0)]
		self.patterns = patterns

		for pi, pat in enumerate(self.patterns):
			self.__add_pattern(pat, pi)
		self.__build_fail_par_and_suf_patterns()
		self.N = len(self.nodes)
		if fail_tree:
			self.build_fail_tree()

	def __add_pattern(self, pat, pi):
		Node, nodes = self.Node, self.nodes

		node = nodes[0]
		for c in pat:
			if c in node:
				node = node[c]
			else:
				new = Node(len(nodes))
				new.trie_par = node
				nodes.append(new)
				node[c] = new
				node = node[c]

		node.rep_patterns.append(pi)
		node.suf_patterns.append(pi)

	def __build_fail_par_and_suf_patterns(self):
		nodes, get_next = self.nodes, self.get_next

		root = nodes[0]
		deq = deque()
		for cn in root.trie_ch.values():
			cn.fail_par = root
			deq.append(cn)

		while deq:
			node = deq.popleft()
			f = node.fail_par
			for c, cn in node.trie_ch.items():
				cn.fail_par = get_next(f, c)
				# 同一の集合は同一のインスタンスを使いまわし、空間をpatternsのサイズに抑える.
				if len(cn.rep_patterns) > 0:
					cn.suf_patterns.extend(cn.fail_par.suf_patterns)
				else:
					cn.suf_patterns = cn.fail_par.suf_patterns
				deq.append(cn)

	def build_fail_tree(self):
		nodes = self.nodes
		if hasattr(nodes[0], "fail_ch"):
			return

		for node in nodes:
			node.fail_ch = []
		for node in nodes[1:]:
			fp = node.fail_par
			fp.fail_ch.append(node)

	def get_next(self, node, c):
		while True:
			if c in node:
				return node[c]
			if node.id == 0:
				return node
			node = node.fail_par

	def explore(self, target):
		nodes, get_next = self.nodes, self.get_next
		node = nodes[0]
		for c in target:
			node = get_next(node, c)
			
			# 途中、根など特定のノードに移動したい時にsendを使用.
			nex = (yield node)
			if nex is not None:
				node = nex

	def calc_dfs_order_on_fail_tree(self):
		nodes = self.nodes
		if not hasattr(nodes[0], "fail_ch"):
			self.build_fail_tree()
		tp = []
		stack = [nodes[0]]
		while stack:
			v = stack.pop()
			tp.append(v)
			for ch in v.fail_ch:
				stack.append(ch)
		return tp

	def calc_all_matching_ranges(self, target):
		explore, patterns = self.explore, self.patterns
		res = []
		for r, node in enumerate(explore(target)):
			for pi in node.suf_patterns:
				res.append((r-len(patterns[pi])+1, r+1, pi))
		return res



def main():
	S = input()
	N = int(input())
	ps = [input() for _ in range(N)]

	aho = AhoCorasick(ps)
	ans = 0
	for node in aho.explore(S):
		ans += len(node.suf_patterns)
	print(ans)

main()
0