前缀总分 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 200 + 100;
const int maxcnt = 200 * 200 + 100;
const int Size = 26;

struct Trie {
    int root, cnt;
    int tree[maxcnt][Size];
    int val[maxcnt];

    int create() {
        ++cnt;
        memset(tree[cnt], 0, sizeof(tree[cnt]));
        val[cnt] = 0;
        return cnt;
    }

    void init() {
        cnt = 0;
        root = create();
    }

    inline int id(const char &ch) {
        return ch - 'a';
    }

    int add(char *s) {
        int ret = 0;
        int pos = root;
        for(int i = 0; s[i] != '\0'; ++i) {
            int w = id(s[i]);
            if(tree[pos][w] == 0) {
                tree[pos][w] = create();
            }
            pos = tree[pos][w];
            ret += val[pos];
            ++val[pos];
        }
        return ret;
    }

    int remove(char *s) {
        int ret = 0;
        int pos = root;
        for(int i = 0; s[i] != '\0'; ++i) {
            int w = id(s[i]);
            pos = tree[pos][w];
            --val[pos];
            ret += val[pos];
        }
        return ret;
    }

    int query(char *s) {
        int ret = 0;
        int pos = root;
        for(int i = 0; s[i] != '\0'; ++i) {
            int w = id(s[i]);
            if (tree[pos][w] == 0) {
                return ret;
            }
            pos = tree[pos][w];
            ret += val[pos];
        }
        return ret;
    }
};

int n, ans, tmp;
char str[maxn][maxn];
Trie t;

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n;
    ans = 0;
    t.init();
    for (int i = 0; i < n; ++i) {
        cin >> str[i];
        ans += t.add(str[i]);
    }
    tmp = ans;
    for (int i = 0; i < n; ++i) {
        tmp -= t.remove(str[i]);
        for (int j = 0; str[i][j] != '\0'; ++j) {
            char ch = str[i][j];
            for (char k = 'a'; k <= 'z'; ++k) {
                str[i][j] = k;
                ans = max(ans, tmp + t.query(str[i]));
            }
            str[i][j] = ch;
        }
        tmp += t.add(str[i]);
    }
    cout << ans << endl;

    return 0;
}