Trie

文字列を 1 文字ずつ木の辺としてたどって登録し、各ノードにそこを通った文字列の個数を持たせます。子は辞書で持つので、文字の種類は問いません（整数のリストやタプルも使えます）。

• Trie(): 空の Trie で初期化
• insert(s): 文字列 $s$ を加える（同じ文字列を何度加えてもよい）。 $O(\lvert s \rvert)$
• erase(s): $s$ を 1 つ削除する。 $s$ が入っていなければ False。 $O(\lvert s \rvert)$
• count(s): $s$ と等しい文字列の個数。 $O(\lvert s \rvert)$
• count_prefix(s): $s$ を接頭辞に持つ文字列の個数。 $O(\lvert s \rvert)$
• lcp(s): 入っている文字列それぞれと $s$ の最長共通接頭辞の長さのうち、最大のもの。 $O(\lvert s \rvert)$
• find(s): $s$ を表すノードの番号（なければ $-1$）。 $O(\lvert s \rvert)$
• nxt[v], cnt[v], end[v]: ノード $v$ の子（文字からノード番号への辞書）、 $v$ を通る文字列の個数、 $v$ で終わる文字列の個数。根は $0$

例（入っている文字列のすべての組について、最長共通接頭辞の長さを足したもの）:

ans = sum(c * (c - 1) // 2 for c in t.cnt[1:])

コード

class Trie:
    def __init__(self):
        self.nxt = [{}]  # nxt[node][c] = 子ノード（根は 0）
        self.cnt = [0]   # そのノードが表す文字列を接頭辞に持つ、入っている文字列の個数
        self.end = [0]   # そのノードが表す文字列と等しい、入っている文字列の個数

    def insert(self, s):
        v = 0
        self.cnt[0] += 1
        for c in s:
            to = self.nxt[v].get(c)
            if to is None:
                to = len(self.cnt)
                self.nxt[v][c] = to
                self.nxt.append({})
                self.cnt.append(0)
                self.end.append(0)
            v = to
            self.cnt[v] += 1
        self.end[v] += 1

    def find(self, s):
        # s を表すノード（なければ -1）
        v = 0
        for c in s:
            v = self.nxt[v].get(c, -1)
            if v == -1:
                break
        return v

    def count(self, s):
        v = self.find(s)
        return 0 if v == -1 else self.end[v]

    def count_prefix(self, s):
        v = self.find(s)
        return 0 if v == -1 else self.cnt[v]

    def erase(self, s):
        # s を 1 つ削除する。s が入っていなければ False
        if self.count(s) == 0:
            return False
        v = 0
        self.cnt[0] -= 1
        for c in s:
            v = self.nxt[v][c]
            self.cnt[v] -= 1
        self.end[v] -= 1
        return True

    def lcp(self, s):
        # 入っている文字列との最長共通接頭辞の長さ
        v = 0
        res = 0
        for c in s:
            v = self.nxt[v].get(c, -1)
            if v == -1 or self.cnt[v] == 0:
                break
            res += 1
        return res