結果
問題 | No.430 文字列検索 |
ユーザー |
![]() |
提出日時 | 2024-07-25 06:01:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 164 ms / 2,000 ms |
コード長 | 3,242 bytes |
コンパイル時間 | 221 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 89,372 KB |
最終ジャッジ日時 | 2024-08-15 16:46:38 |
合計ジャッジ時間 | 2,764 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
76,996 KB |
testcase_01 | AC | 36 ms
55,928 KB |
testcase_02 | AC | 164 ms
89,372 KB |
testcase_03 | AC | 101 ms
79,496 KB |
testcase_04 | AC | 99 ms
79,440 KB |
testcase_05 | AC | 36 ms
55,004 KB |
testcase_06 | AC | 35 ms
54,700 KB |
testcase_07 | AC | 34 ms
55,076 KB |
testcase_08 | AC | 35 ms
55,688 KB |
testcase_09 | AC | 66 ms
76,188 KB |
testcase_10 | AC | 49 ms
66,440 KB |
testcase_11 | AC | 59 ms
71,828 KB |
testcase_12 | AC | 159 ms
84,908 KB |
testcase_13 | AC | 158 ms
86,188 KB |
testcase_14 | AC | 161 ms
86,188 KB |
testcase_15 | AC | 143 ms
83,624 KB |
testcase_16 | AC | 136 ms
81,344 KB |
testcase_17 | AC | 142 ms
81,592 KB |
testcase_18 | AC | 127 ms
81,340 KB |
ソースコード
""" 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()