AC成功 空间击败100%

AC成功
空间击败100%

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

const int MOD1 = 1000000007;
const int MOD2 = 1000000009;
const int BASE = 131;
const int MAXL = 1000000 + 5;

vector<int> pow1(MAXL), pow2(MAXL);

struct Key {
    uint64_t h;
    int len;
    bool operator==(const Key& other) const {
        return h == other.h && len == other.len;
    }
};

struct KeyHash {
    size_t operator()(const Key& k) const {
        return k.h ^ (k.h >> 33) ^ (static_cast<size_t>(k.len) * 1000003);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    pow1[0] = pow2[0] = 1;
    for (int i = 1; i < MAXL; ++i) {
        pow1[i] = (long long)pow1[i - 1] * BASE % MOD1;
        pow2[i] = (long long)pow2[i - 1] * BASE % MOD2;
    }

    int N;
    cin >> N;
    vector<string> strs(N);

    unordered_set<Key, KeyHash> hashSet;
    hashSet.reserve(N * 2 + 10);
    hashSet.max_load_factor(0.7);

    for (int i = 0; i < N; ++i) {
        cin >> strs[i];
        const string& s = strs[i];
        int h1 = 0, h2 = 0;
        for (char ch : s) {
            int val = ch - 'a' + 1;
            h1 = ((long long)h1 * BASE + val) % MOD1;
            h2 = ((long long)h2 * BASE + val) % MOD2;
        }
        uint64_t key = ((uint64_t)h1 << 32) | (uint32_t)h2;
        hashSet.insert({key, (int)s.size()});
    }

    long long ans = 0;

    for (const string& s : strs) {
        int n = (int)s.size();
        if (n <= 1) continue;

        vector<int> pre1(n + 1), pre2(n + 1), mask(n + 1);
        pre1[0] = pre2[0] = 0;
        mask[0] = 0;

        for (int i = 0; i < n; ++i) {
            int val = s[i] - 'a' + 1;
            pre1[i + 1] = ((long long)pre1[i] * BASE + val) % MOD1;
            pre2[i + 1] = ((long long)pre2[i] * BASE + val) % MOD2;
            mask[i + 1] = mask[i] | (1 << (s[i] - 'a'));
        }

        int totalMask = mask[n];

        // 长度为 1 的可达字符串
        int m = totalMask;
        while (m) {
            int c = __builtin_ctz(m);
            m &= m - 1;
            int val = c + 1;
            uint64_t hkey = ((uint64_t)val << 32) | (uint32_t)val;
            if (hashSet.find({hkey, 1}) != hashSet.end()) {
                ++ans;
            }
        }

        // 长度 >= 2 的可达字符串：c + suffix
        // p2 是后缀的起始位置，suffix = s[p2..n-1]
        for (int p2 = 2; p2 < n; ++p2) {
            int lenSuf = n - p2;

            int suf1 = (pre1[n] - (long long)pre1[p2] * pow1[lenSuf] % MOD1 + MOD1) % MOD1;
            int suf2 = (pre2[n] - (long long)pre2[p2] * pow2[lenSuf] % MOD2 + MOD2) % MOD2;

            int availMask = mask[p2]; // 前缀 s[0..p2-1] 中出现的字符
            int m2 = availMask;
            while (m2) {
                int c = __builtin_ctz(m2);
                m2 &= m2 - 1;
                int val = c + 1;

                int h1 = ((long long)val * pow1[lenSuf] + suf1) % MOD1;
                int h2 = ((long long)val * pow2[lenSuf] + suf2) % MOD2;
                uint64_t hkey = ((uint64_t)h1 << 32) | (uint32_t)h2;

                int targetLen = 1 + lenSuf;
                if (hashSet.find({hkey, targetLen}) != hashSet.end()) {
                    ++ans;
                }
            }
        }
    }

    cout << ans << '\n';
    return 0;
}