#include <bits/stdc++.h> const int maxn = 2e5 + 5; using namespace std; struct Trie{ int nex[maxn][26], fail[maxn], end[maxn]; int root, p; inline int newnode() { for (int i = 0; i < 26; ++i) { nex[p][i] = -1; } end[p++] = 0; return p - 1; } inline void init() { p = 0; root = newnode(); } inline void insert(char *buf) { int now = root; for (int i = 0; buf[i]; ++i) { if (nex[now][buf[i]-'a'] == -1) nex[now][buf[i]-'a'] = newnode(); now = nex[now][buf[i]-'a']; } end[now]++; } inline void build() { queue<int> que; fail[root] = root; for (int i = 0; i < 26; ++i) { if (nex[root][i] == -1) nex[root][i] = root; else { fail[nex[root][i]] = root; que.push(nex[root][i]); } } while (!que.empty()) { int now = que.front(); que.pop(); for (int i = 0; i < 26; ++i) { if (nex[now][i] == -1) nex[now][i] = nex[fail[now]][i]; else { fail[nex[now][i]] = nex[fail[now]][i]; que.push(nex[now][i]); } } } } }L, R;
No Leanote account ? Sign up now.