結果

問題 No.2761 Substitute and Search
ユーザー maguroflymagurofly
提出日時 2024-04-30 00:02:15
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,043 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 963,372 KB
最終ジャッジ日時 2024-11-29 18:10:44
合計ジャッジ時間 39,954 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
59,764 KB
testcase_01 MLE -
testcase_02 AC 38 ms
59,772 KB
testcase_03 MLE -
testcase_04 AC 548 ms
112,920 KB
testcase_05 MLE -
testcase_06 TLE -
testcase_07 MLE -
testcase_08 AC 503 ms
156,988 KB
testcase_09 MLE -
testcase_10 TLE -
testcase_11 MLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 AC 595 ms
151,060 KB
testcase_15 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def convert(str):
    return [ord(str[i]) - 0x61 for i in range(len(str))]

N, L, Q = map(int, input().split())
S = [convert(input().strip()) for _ in range(N)]

class Node:
    __slots__ = ("sum", "children", "parent")
    def __init__(self):
        self.sum = 0
        self.children = [None] * 26
        self.parent = None

# (sum, children, parent)
trie = Node()
by_index_char = [[{} for _ in range(26)] for _ in range(L)]

def add(str, amount = 1):
    cur = trie
    cur.sum += amount
    for i in range(L):
        c = str[i]
        if not cur.children[c]:
            node = Node()
            node.parent = cur
            cur.children[c] = node
            by_index_char[i][c][id(node)] = node
        cur = cur.children[c]
        cur.sum += amount

def substitute(k, c, d):
    stack = []
    for node in by_index_char[k][c].values():
        parent = node.parent
        if not parent: continue
        parent.children[c] = None
        if merged := parent.children[d]:
            stack.append((node, merged, k))
        else:
            parent.children[d] = node
            by_index_char[k][d][id(node)] = node
    by_index_char[k][c].clear()
    while stack:
        src, dst, k = stack.pop()
        dst.sum += src.sum
        for c in range(26):
            if src_child := src.children[c]:
                if dst_child := dst.children[c]:
                    by_index_char[k + 1][c].pop(id(src_child))
                    stack.append((src_child, dst_child, k + 1))
                else:
                    src_child.parent = dst
                    dst.children[c] = src_child

def count_prefix(t):
    cur = trie
    for c in t:
        cur = cur.children[c]
        if not cur:
            return 0
    return cur.sum

for s in S:
    add(s)

for _ in range(Q):
    values = input().split()
    if values[0] == "1":
        k = int(values[1]) - 1
        c = ord(values[2]) - 0x61
        d = ord(values[3]) - 0x61
        substitute(k, c, d)
    else:
        t = convert(values[1])
        print(count_prefix(t))
0