結果

問題 No.430 文字列検索
ユーザー 前田悠真
提出日時 2025-09-10 23:55:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 138 ms / 2,000 ms
コード長 1,474 bytes
コンパイル時間 355 ms
コンパイル使用メモリ 81,976 KB
実行使用メモリ 84,608 KB
最終ジャッジ日時 2025-09-10 23:55:20
合計ジャッジ時間 3,487 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
class AhoCorasick:
  def __init__(self, size=26, base='a'):
    self.node=[[-1]*size]
    self.par=[-1]
    self.last=[0]
    self.size=size
    self.base=ord(base)
    self.built=False

  def add(self, s: str) -> int:
    assert self.built is False
    v=0
    for c in s:
      i=ord(c)-self.base
      if self.node[v][i]==-1:
        self.node[v][i]=len(self.node)
        self.node.append([-1]*self.size)
        self.par.append(v)
        self.last.append(0)
      v = self.node[v][i]
    self.last[v] += 1
    return v

  def build(self) -> None:
    assert self.built is False
    link=[0]*len(self.node)
    q=deque()
    for i in range(self.size):
      if self.node[0][i]==-1:
        self.node[0][i]=0
      else:
        link[self.node[0][i]]=0
        q.append(self.node[0][i])

    while q:
      v=q.popleft()
      self.last[v] += self.last[link[v]]
      for i in range(self.size):
        u=self.node[v][i]
        if u==-1:
          self.node[v][i]=self.node[link[v]][i]
        else:
          link[u]=self.node[link[v]][i]
          q.append(u)
    self.link=link
    self.built=True

S = input()
aho = AhoCorasick(26, 'A')
n = int(input())
A = [input() for _ in range(n)]
for i in range(n):
  aho.add(A[i])
aho.build()
u = 0
ans = 0
# print(aho.last)
for i in range(len(S)):
  v = ord(S[i])-ord('A')
  if aho.node[u][v]==-1:
    u = 0
  else:
    u = aho.node[u][v]
  ans += aho.last[u]
  # print(i, ans)

print(ans)
0