結果

問題 No.430 文字列検索
コンテスト
ユーザー aaaaa
提出日時 2021-08-12 16:17:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 188 ms / 2,000 ms
コード長 3,787 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 111,360 KB
最終ジャッジ日時 2024-11-10 00:57:12
合計ジャッジ時間 2,633 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

class Trie:
    def __init__(self, base=ord("a"), char_size=26):
        self.nexts = []
        self.accepts = []
        self.cs = []
        self.commons = []
        self.base = base
        self.char_size = char_size
        self.root = 0
        self.words = defaultdict(set)
        self._construct_node(self.root)

    def _construct_node(self, n):
        for i in range(self.char_size):
            self.nexts.append(-1)
        self.accepts.append(0)
        self.cs.append(n)
        self.commons.append(0)

    def insert(self, word):
        node_id = self.root
        for i in range(len(word)):
            c = ord(word[i])-self.base
            next_id = self.nexts[self.char_size*node_id+c]
            if next_id == -1:
                next_id = len(self.cs)
                self.nexts[self.char_size*node_id+c] = next_id
                self._construct_node(c)
            self.commons[node_id] += 1
            node_id = next_id

        self.commons[node_id] += 1
        self.accepts[node_id] += 1
        return node_id

    def search(self, word, prefix=False):
        node_id = self.root
        for i in range(len(word)):
            c = ord(word[i]) - self.base
            next_id = self.nexts[self.char_size*node_id+c]
            if next_id == -1:
                return False
            node_id = next_id
        if prefix:
            return True
        return self.accepts[node_id] > 0
    
    def size(self):
        return len(self.cs)
    
    def count(self):
        return self.commons[0]

from collections import deque, defaultdict

class AhoCorasickTrie(Trie):
    def __init__(self, patterns, base=ord("a"), char_size=26):
        super().__init__(base, char_size)
        self.patterns = patterns
        self.pattern_len = [len(pat) for pat in patterns]
        self.matches = defaultdict(set)
        for i, pat in enumerate(patterns):
            node_id = self.insert(pat)
            self.matches[node_id].add(i)
        self.back_edge = self._BFS()

    def _BFS(self):
        back_edge = [0]*self.size()

        Q = deque([])

        for i in range(self.char_size):
            v1 = self.nexts[self.char_size*self.root+i]
            if v1 != -1:
                Q.append(v1)
                back_edge[v1] = self.root

        while len(Q) > 0:
            v = Q.pop()
            if self.commons[v] == 0:
                continue
            for i in range(self.char_size):
                v1 = self.nexts[self.char_size*v+i]
                if v1 != -1:
                    back = back_edge[v]
                    while self.nexts[self.char_size*back+i] == -1 and back != self.root:
                        back = back_edge[back]
                    if self.nexts[self.char_size*back+i] == -1:
                        back_edge[v1] = self.root
                    else:
                        back_edge[v1] = self.nexts[self.char_size*back+i]
                        self.matches[v1] |= self.matches[back_edge[v1]]
                    Q.appendleft(v1)
        return back_edge        
        
    def match(self, S):
        now = self.root
        match_list = defaultdict(list)
        for i in range(len(S)):
            c = ord(S[i]) - self.base
            while self.nexts[self.char_size*now+c] == -1 and now != self.root:
                now = self.back_edge[now]
            if self.nexts[self.char_size*now+c] != -1:
                now = self.nexts[self.char_size*now+c]
                for pat in self.matches[now]:
                    match_list[pat].append(i-self.pattern_len[pat]+1)
        return match_list

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

act = AhoCorasickTrie(C, base=ord("A"))

res = act.match(S)

print(sum(len(c) for _,c in res.items()))
0