ABC353E字典树处理最长公共前缀

https://atcoder.jp/contests/abc353/tasks/abc353_e

其实就是字典树板子题。

似乎遇到最长公共前缀，就该想到字典树。

依次加入每个字符串：

维护一个数组 siz 来统计在当前串之前的串在对应点的出现次数。

手模一下字典树的建树过程，显然如果当前串 \(S_i\) 能跑到一个曾经串 \(S_j\) 也出现过的点，那么这一个点肯定是 \(S_i\) 和 \(S_j\) 最长公共前缀的一部分，所以全部加入答案。

template <typename T>
struct Trie {
    int m;
    int N = 2e6;
    int now, tot;
    i64 ans;
    std::vector<T> val;
    std::vector<int> siz;//用来维护在加入这个字符串之前有多少个字符串到过字典树的这个位置
    std::vector<std::map<T, int> > nxt;
    Trie():val(N), siz(1, 0), tot(1), nxt(1, std::map<T, int>()), ans(0){}

    void add(std::string s) {
        now = 0;
        for (int i = 0; i < s.size(); i++){
            if (nxt[now][s[i]] == 0) {
                nxt[now][s[i]] = tot; siz.push_back(0); val[tot++] = s[i];
            }
            now = nxt[now][s[i]];
            ans += siz[now];//只要当前这个字符串也能到，那肯定是和之前字符串的公共前缀的一部分，加入进去
            siz[now] += 1;
            nxt.push_back(std::map<T, int>());
        }
    }
};

signed main() {

    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;
    Trie<char> trie;
    std::string s;
    for (int i = 0; i < n; i++) {
        std::cin >> s;
        trie.add(s);
    }

    std::cout << trie.ans << '\n';

    return 0;
}