const int N = 1e6;

// Бор от всех словарных слов
int next[N][26]; // next[v][c] = 0 : нет ребра
int suf[N];

int isEnd[N];

isEnd[v] = isTerminal[v] || isEnd[suf[v]];

// O(|text|)
void find(string &text) {
	int v = root;
	for (char c : text) {
		int i = c - 'a';
		while (v != root && next[v][i] == 0)
			v = suf[v]; // v --> pi[v]
		if (next[v][i] != 0)
			v = next[v][i]; // ++длины
		// v = go[v][i];
		if (isEnd[v])
			; // я нашёл словарное слово
			// какое-то, какое пока не знаю
	}
}

void calcSuf(int v) {
	int c = pc[v], x = suf[p[v]];
	while (x != root && next[x][c] == 0)
		x = suf[x]; // перебираем все суффиксы p[v]
	if (next[x][c])
		x = next[x][c];
	suf[v] = x;//go[x][c];
}
void calcGo(int v, int c) {
	if (next[v][c])
		go[v][c] = next[v][c];
	else
		go[v][c] = go[suf[v]][c];

	// |str(suf[v])| < |str(v)|
}

// Построить полный "автомат"
for v : в порядке возрастания глубины // (от корня к листьям)
	calcSuf(v) // suf[v]
	for c
		calcGo(v, c) // go[v][c]

// Ленивая динамика: сосчитать только нужные suf[] и go[]
int getSuf(int v) {
	if (suf[v] == -1)
		suf[v] = v == root ? root : getGo(getSuf(p[v]), pc[v]);
	return suf[v]
}
int getGo(int v, int c) {
	if (go[v][c] == -1)
		go[v][c] = next[v][c] ? next[v][c] : getGo(getSuf(v), c);
	return go[v][c];
}