JZTXT

ybtoj字典树练习

发布时间 2023-09-14 15:27:12作者: jt0007

E. 1.单词拼接

纯狗题，本题交了52发，谁看这个数据范围谁倒霉，真的我祝出题人幸福，看到5e3我果断开始map复杂度\(O(n^2logn)\)

#include <bits/stdc++.h>
using namespace std;
map<string, int> mp;
const int maxn = 5e3 + 5;
string s[maxn];
map<string, int> mp2;
signed main() {
    int now = 1;
    while (cin >> s[now]) {
        mp[s[now]] = 1;
        now++;
    }
    s[now] += '$';
    for (int i = 1; i < now; i++) {
        for (int j = 1; j <= now; j++) {
            if (i == j)
                continue;
            string s2;
            s2 += (s[i] + s[j]);
            mp2[s2] = 1;
        }
    }
    for (int i = 1; i < now; i++) {
        if (mp2[s[i]] == 1) {
            cout << s[i] << '\n';
        }
    }
    return 0;
}

但是re了在我疯狂cerr后发现数据范围是\(3e4\)级别，所以这个做法T了...

正确做法：

先把所有字符串塞到trie树里，然后暴力拆分到树里匹配复杂度\(O(n)\)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
int tr[maxn][200];
int tot;
char c[maxn][250];
int ed[maxn];
int getnum(char c) { return (int)(c - '0'); }
void insert(char *s) {
    int p = 0;
    for (int i = 0; i < strlen(s); i++) {
        int k = getnum(s[i]);
        if (!tr[p][k]) {
            tr[p][k] = ++tot;
        }
        p = tr[p][k];
    }
    ed[p]++;
}
bool find(char *s, int l, int r) {
    if (l > r)
        return 0;
    int p = 0;
    for (int i = l; i <= r; i++) {
        int k = getnum(s[i]);
        if (!tr[p][k]) {
            return 0;
        }
        p = tr[p][k];
    }

    return ed[p];
}
signed main() {
    int now = 0;
    while (cin >> c[++now]) {
        insert(c[now]);
    }
    for (int i = 1; i <= now; i++) {
        int len = strlen(c[i]);
        for (int k = 0; k < len - 1; k++) {
            if (find(c[i], 0, k) && find(c[i], k + 1, len - 1)) {
                cout << c[i] << '\n';
                break;
            }
        }
    }
}