結果

問題 No.430 文字列検索
コンテスト
ユーザー 👑 loop0919
提出日時 2026-01-02 17:18:27
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 213 ms / 2,000 ms
コード長 3,912 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 483 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 92,516 KB
最終ジャッジ日時 2026-01-02 17:18:31
合計ジャッジ時間 3,789 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque
from string import ascii_lowercase, ascii_uppercase
from typing import Iterable, TypeVar

T = TypeVar("T")


class AhoCorasick:
    """\
    Aho-Corasick 法
    
    text 中に含まれる複数の pattern を検索するアルゴリズム
    
    Usage::

        from string import ascii_uppercase

        ac = AhoCorasick(ascii_uppercase)

        ac.add("ABC")
        ac.add("B")
        ac.add("ZZZZZ")

        ac.build()

        print(ac.find_all("XBABABCDEX"))
        # => [[4], [1, 3, 5], []]
    """

    # Aho-Corasick グラフにおける根の頂点番号
    ROOT: int = 0

    # 文字の種類数
    sigma: int

    # Aho-Corasick グラフ
    graph: list[list[int | None]]

    # 頂点番号と検索パターン文字列の suffix の対応
    end: list[set[int]]

    # 各検索パターン文字列の長さ
    length: list[int]

    def __init__(self, letters: Iterable[T] = ascii_lowercase):
        """\
        Aho-Corasick 法
        
        Args::
        
            letters: 使用する文字の種類 (デフォルト: 英小文字)
        """
        self.sigma = len(letters)
        self.to_index = {s: i for i, s in enumerate(letters)}

        self.graph = [[None] * self.sigma]
        self.end = [set()]
        self.length = []

    def add(self, pattern: Iterable[T]):
        """\
        検索したい文字列 pattern を追加する
        
        Args::
        
            pattern: 検索したい文字列
        
        Complexity::
        
            O(sigma * len(pattern))
        """
        self.length.append(len(pattern))
        self._add(pattern, len(self.length) - 1)

    def _add(self, S: Iterable[T], id: int):
        curr = self.ROOT
        for s in S:
            index = self.to_index[s]
            if (to := self.graph[curr][index]) is None:
                self.graph.append([None] * self.sigma)
                self.end.append(set())

                to = len(self.graph) - 1
                self.graph[curr][index] = to

            curr = to

        self.end[curr].add(id)

    def build(self):
        """\
        Aho-Corasick グラフを構築する
        
        Complexity::
        
            O(sigma * sum(len(pattern)))
        """
        link = [self.ROOT] * len(self.graph)
        que: deque[int] = deque()

        for i in range(self.sigma):
            if self.graph[self.ROOT][i] is None:
                self.graph[self.ROOT][i] = self.ROOT
            else:
                link[self.graph[self.ROOT][i]] = self.ROOT
                que.append(self.graph[self.ROOT][i])

        while que:
            curr = que.popleft()
            self.end[curr].update(self.end[link[curr]])

            for i in range(self.sigma):
                to = self.graph[curr][i]

                if to is None:
                    self.graph[curr][i] = self.graph[link[curr]][i]
                else:
                    link[to] = self.graph[link[curr]][i]
                    que.append(to)

    def find_all(self, text: Iterable[T], start: int = 0) -> list[list[int]]:
        """\
        各パターンについて、text 中に含まれるパターンの開始位置の配列を返す
        
        Args::
        
            text: 文字列
        
        Complexity::
        
            O(len(text) + sum(len(pattern)) + match回数)
        """

        found = [[] for _ in range(len(self.length))]
        curr = start

        for i, char in enumerate(text):
            index = self.to_index[char]

            curr = self.graph[curr][index]
            for pattern_id in self.end[curr]:
                found[pattern_id].append(i - self.length[pattern_id] + 1)

        return found


S = input()
M = int(input())

ac = AhoCorasick(ascii_uppercase)

for _ in range(M):
    C = input()
    ac.add(C)

ac.build()
print(sum(len(f) for f in ac.find_all(S)))
0