1. 首页
2. 字典树
3. 本页

UVALive 5913 Dictionary Size (字典树)

题意：~

思路：

#include <bits/stdc++.h>

using namespace std;

const int N = 400050;

struct Trie {
    int next[N][26];
    int root, L;
    int num[26];
    int newnode()
    {
        for(int i = 0;i < 26; ++i)
            next[L][i] = -1;
        L++;
        return L - 1;
    }
    void init()
    {
        L = 0;
        root = newnode();
        fill(num, num + 26, 0);
    }
    void insert(string buf)
    {
        int now = root;
        bool f = false;
        for(auto &i : buf)
        {
            if(next[now][i - 'a'] == -1)
            {
                next[now][i - 'a'] = newnode();
                if(f) num[i - 'a']++;
            }
            now = next[now][i - 'a']; f = true;
        }
    }
};

Trie ac, wa;
bool vis[26];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin >> n)
    {
        ac.init();
        wa.init();
        string str;
        fill(vis, vis + 26, false);
        long long ans = 0;
        for(int i = 0; i < n; ++i)
        {
            cin >> str;
            if(str.size() == 1)
            {
                if(!vis[str[0] - 'a'])
                {
                    vis[str[0] - 'a'] = 1;
                    ans++;
                }
            }
            ac.insert(str);
            reverse(str.begin(), str.end());
            wa.insert(str);
        }
        ans += (long long)(ac.L - 1) * (wa.L - 1);
        for(int i = 0; i < 26; ++i)
            ans -= (long long)ac.num[i] * wa.num[i];
        cout << ans << endl;
    }
    return 0;
}