結果

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

ソースコード

diff #
raw source code 

from collections import deque

class AhoCorasick:
    def __init__(self, type):
        self.next = [[-1]*26]
        self.link = [-1]
        self.out = [[]]
        self.size = 1
        self.base = ord("a") if type == 0 else ord("A")
    
    def code(self, s):
        return ord(s)-self.base

    def add_word(self, word, idx):
        """
        word を trie に追加
        idx はそのパターンの識別子（番号とか）
        """
        v = 0
        for c in word:
            if self.next[v][self.code(c)] == -1:
                self.next[v][self.code(c)] = self.size
                self.next.append([-1]*26)
                self.link.append(0)
                self.out.append([])
                self.size += 1
            v = self.next[v][self.code(c)]
        self.out[v].append(idx)

    def build(self):
        que = deque()
        for i in range(26):
            if self.next[0][i] != -1:
                self.link[self.next[0][i]] = 0
                que.append(self.next[0][i])
        while que:
            n = que.popleft()
            for i in range(26):
                if self.next[n][i] != -1:
                    f = self.link[n]
                    while f != -1 and self.next[f][i] == -1:
                        f = self.link[f]
                    if f == -1:
                        self.link[self.next[n][i]] = 0
                    else:
                        self.link[self.next[n][i]] = self.next[f][i]
                    self.out[self.next[n][i]].extend(self.out[self.link[self.next[n][i]]])
                    que.append(self.next[n][i])

    def match(self, text):
        res = []
        n = 0
        for i, c in enumerate(text):
            while n != 0 and self.next[n][self.code(c)] == -1:
                n = self.link[n]
            if self.next[n][self.code(c)] != -1:
                n = self.next[n][self.code(c)]
            for idx in self.out[n]:
                res.append((i, idx))
        return res

def code(s):
    return ord(s)-ord("A")

S = input()
M = int(input())
C = [input() for _ in range(M)]

AC = AhoCorasick(1)
for i, c in enumerate(C):
    AC.add_word(c, i)
AC.build()

ans = 0
now = 0
for s in S:
    while now != 0 and AC.next[now][code(s)] == -1:
        now = AC.link[now]
    if AC.next[now][code(s)] != -1:
        now = AC.next[now][code(s)]
    ans += len(AC.out[now])

print(ans)
0