记得平衡复杂度

又及: 这是一个悲惨的故事: 我又忘push

懵逼的 题目

BZOJ

扯淡的 题解

这题暴跳fail也才$\mathrm O(2 \times 10^8)$不是…

那写啥正解啊

预处理fail的时候要把终点标记沿着fail下放, 不然复杂度就是$\mathrm O(10^{10})$左右了

沙茶的 代码

/**************************************************************
    Problem: 3172
    User: Cansult
    Language: C++
    Result: Accepted
    Time:3292 ms
    Memory:182656 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (1000200 + 5)
#define MAXC (27)
using namespace std;
struct node {
    int son[MAXC], fail;
    vector<int> bh;
} b[MAXN];
int ans[MAXN], cntb, n, ns;
char s[MAXN], sn[MAXN];
void init() {
    queue<int> q;
    for (int i = 0; i < MAXC; i++) if (b[0].son[i]) q.push(b[0].son[i]);
    while (!q.empty()) {
        int dq = q.front();
        q.pop();
        for (int i = 0; i < b[b[dq].fail].bh.size(); i++)
            b[dq].bh.push_back(b[b[dq].fail].bh[i]);
        for (int i = 0; i < MAXC; i++)
            if (b[dq].son[i]) b[b[dq].son[i]].fail = b[b[dq].fail].son[i], q.push(b[dq].son[i]);
            else b[dq].son[i] = b[b[dq].fail].son[i];
    }
}
void pd(int dq) {
    for (int j = 0; j < b[dq].bh.size(); j++)
        ++ans[b[dq].bh[j]];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        int dqn = strlen(s), dq = 0;
        for (int j = 0; j < dqn; j++) {
            if (!b[dq].son[s[j] - 'a']) b[dq].son[s[j] - 'a'] = ++cntb;
            dq = b[dq].son[s[j] - 'a'];
            sn[++ns] = s[j];
        }
        b[dq].bh.push_back(i);
        sn[++ns] = 'a' + 26;
    }
    init();
    for (int i = 0, dq = 0; i < ns; i++) 
        if (sn[i] <= 'z')
            pd(dq = b[dq].son[sn[i] - 'a']);
        else dq = 0;
    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}

By 准备退役旅游的 Cansult