题解 P4421 [COCI2017-2018#1] Lozinke

xiezheyuan · 2024-09-15 14:19:13 · 题解

首先发现字符串长度过小，可以考虑一些基于字符串长度暴力的做法。

我们枚举每一个字符串，将其插入到 Trie 中，标记每个节点做了多少次字符串的终结节点。

然后还是枚举每一个字符串，再枚举字符串的每一个前缀，前缀的前缀可以覆盖到所有子串，我们将这个前缀放到 Trie 上查询，每次遇到一个 Trie 上的节点就贡献答案，然后如果 Trie 上没有对应的节点了就返回。

注意到你可能会算重，所以对于枚举的每一个字符串，用 map 来去重。

时间复杂度 O({nL^2\log L})，其中 L 为字符串的长度。

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

const int N = 4e5 + 5;
int n;
string s[N];

int t[N][26], ec = 1, val[N];

void insert(string s){
    int cur = 0;
    for(char i : s){
        if(!t[cur][i - 'a']) t[cur][i - 'a'] = ++ec;
        cur = t[cur][i - 'a'];
    }
    val[cur]++;
}

map<int,int> zak;

int query(string s){
    int cur = 0, ans = 0;
    for(char i : s){
        if(!t[cur][i - 'a']) return ans;
        cur = t[cur][i - 'a'];
        if(!zak[cur]){
            ans += val[cur];
            zak[cur] = 1;
        }
    }
    return ans;
}

signed main(){
    #ifdef LOCAL
    freopen("bug.in", "r", stdin);
    freopen("bug.out", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> s[i];
        insert(s[i]);
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        zak.clear();
        for(unsigned j=0;j<s[i].size();j++){
            string zky;
            for(unsigned k=j;k<s[i].size();k++) zky += s[i][k];
            // cout << i << ' ' << j <<  ' ' << query(zky) << '\n';
            ans += query(zky) - (j == 0);
        }
    }
    cout << ans;
    return 0;
}

// Written by xiezheyuan
···