Codeforces 291E KMP + DFS

Codeforces 291E KMP + DFS 题意

传送门 Codeforces 291E Tree-String Problem

题解

K M P KMP KMP 构建自动机。将 s i s_i si​ 看作 i i i 的点权， D F S DFS DFS 统计即可。总时间复杂度 O ( ∣ t ∣ + ∑ ∣ s i ∣ ) O(lvert trvert+sumlvert s_irvert) O(∣t∣+∑∣si​∣)。

#include 
using namespace std;
#define rep(i, l, r) for (int i = l, _ = r; i < _; ++i)
const int MAXN = 3E5 + 5;
vector G[MAXN];
string S[MAXN], T;
int N, B[MAXN], aut[MAXN][26];

void kmp(string &s, int b[])
{
    int n = s.size();
    int i = 0, j = -1;
    b[i] = j;
    while (i < n)
    {
        while (j >= 0 && s[i] != s[j])
            j = b[j];
        ++i, ++j;
        b[i] = j;
    }
    rep(i, 0, n) rep(j, 0, 26) aut[i][j] = s[i] - 'a' == j ? i + 1 : (b[i] == -1 ? 0 : aut[b[i]][j]);
}

void dfs(int u, int s, int &res)
{
    for (auto &c : S[u])
    {
        s = aut[s][c - 'a'];
        if (s == (int)T.size())
            ++res, s = B[s];
    }
    for (auto &v : G[u])
        dfs(v, s, res);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N;
    rep(i, 1, N)
    {
        int p;
        cin >> p >> S[i];
        G[p - 1].push_back(i);
    }
    cin >> T;
    kmp(T, B);
    int res = 0;
    dfs(0, 0, res);
    cout << res << 'n';
    return 0;
}