Побудуємо автомат Ахо — Корасік для множини зразків. Сумарна довжина зразків не перевищує 5 \cdot 10^5, тому бор містить не більше 5 \cdot 10^5 + 1 вершин. Алфавіт складається з малих латинських літер. Вершину, в якій закінчується зразок, позначимо як термінальну, а для кожного зразка зберігатимемо номер його кінцевої вершини . Однакові зразки закінчуються в одній і тій самій вершині.
Обробка тексту. Пропустимо текст через автомат. Нехай після зчитування чергового символу автомат перебуває у вершині . Тоді вершини на ланцюжку суфіксних посилань v \to \mathit{link}[v] \to \ldots \to 0 відповідають усім суфіксам уже зчитаного тексту, які є префіксами зразків. Зразок зустрічається в тексті та закінчується на поточній позиції тоді й лише тоді, коли його кінцева вершина лежить на цьому ланцюжку. Отже, достатньо позначити прапорцем усі вершини, через які проходять ланцюжки суфіксних посилань. Відповідь для зразка — це значення .
Чому не можна проходити весь ланцюжок. Довжина ланцюжка може бути порядку довжини зразка. Наприклад, для зразків , , , і тексту на кожній позиції довелося б проходити довгий ланцюжок, і сумарний час був би O(n \cdot L), де — довжина найдовшого зразка. Тому проходження ланцюжка зупиняється у двох випадках:
\mathit{term}[u] = \textbf{\textit{false}}: прапорець \mathit{term}[u] = \mathit{term}[u] \lor \mathit{term}[\mathit{link}[u]] обчислюється під час побудови автомата і означає, що ланцюжок від містить хоча б одну термінальну вершину. Якщо він хибний, подальших кінців зразків на ланцюжку немає;
\mathit{vis}[u] = \textbf{\textit{true}}: вершину вже відвідано, а отже, весь ланцюжок від до першої вершини з \mathit{term} = \textbf{\textit{false}} також уже пройдено.
Друге твердження справедливе, оскільки при позначенні вершини проходження завжди продовжується вздовж її суфіксного посилання і зупиняється лише у вершині з \mathit{term} = \textbf{\textit{false}} або у вже позначеній вершині. Таким чином, кожна вершина позначається не більше одного разу.
Складність. Побудова автомата займає O(V \cdot 26), де V \le 5 \cdot 10^5 + 1 — кількість вершин бору. Обробка тексту займає переходів плюс позначень, а відповіді виводяться за . Масив переходів займає приблизно 5 \cdot 10^5 \cdot 26 \cdot 4 байт МБ.
Приклад
Текст — , зразки — , , . Вставимо зразки в бор у заданому порядку. Номери вершин відповідають порядку їх створення, під кожною вершиною записано відповідний їй рядок, а термінальні вершини виділено: \mathit{endNode} = (3, 6, 9).
Суфіксні посилання, що не ведуть до кореня:
\mathit{link}(ba) = a, тобто \mathit{link}[2] = 4;
\mathit{link}(ab) = b, тобто \mathit{link}[5] = 1;
\mathit{link}(bab) = ab, тобто \mathit{link}[3] = 5;
\mathit{link}(ayb) = b, тобто \mathit{link}[8] = 1;
\mathit{link}(ayba) = ba, тобто \mathit{link}[9] = 2.
Жодне суфіксне посилання не веде до термінальної вершини, тому \mathit{term} = \textbf{\textit{true}} лише у вершинах , та .
Пропустимо текст через автомат. Під кожним символом показано вершину, в якій опиняється автомат після його зчитування.
символ | рядок вершини | позначені вершини | ||
0 | 4 | — | ||
1 | 7 | — | ||
2 | 8 | — | ||
3 | 9 | 9 () | ||
4 | 3 | 3 () | ||
5 | 0 | — | ||
6 | 0 | — |
Після символу з індексом автомат перебуває у термінальній вершині (): її позначають, а проходження ланцюжка зупиняється у вершині \mathit{link}[9] = 2, для якої \mathit{term}[2] = \textbf{\textit{false}}. Наступний символ — : у борі немає переходу з вершини за символом , тому за суфіксним посиланням автомат переходить у вершину \mathit{go}[2][b] = 3 (), яку також позначають. Вершину () не позначають жодного разу.
Відповідь: \mathit{vis}[3] = \textbf{\textit{true}}, \mathit{vis}[6] = \textbf{\textit{false}}, \mathit{vis}[9] = \textbf{\textit{true}}, тобто YES, NO, YES.
Зупинка проходження за прапорцем . Розглянемо зразки , , і текст . Бор являє собою ланцюжок вершин (), (), (), усі вони термінальні, а суфіксні посилання ведуть 3 \to 2 \to 1 \to 0.
крок | проходження ланцюжка | позначено | |
1 | 1 | 1 \to 0 (\mathit{term}[0] = \textit{false}) | 1 |
2 | 2 | 2 \to 1 (\mathit{vis}[1] = \textit{true}) | 2 |
3 | 3 | 3 \to 2 (\mathit{vis}[2] = \textit{true}) | 3 |
4 | 3 | (\mathit{vis}[3] = \textit{true}) | — |
Кожну вершину позначають рівно один раз. Без прапорця , починаючи з другого кроку, щоразу довелося б знову проходити ланцюжок аж до кореня.
Реалізація алгоритму
Оголосимо константи: розмір алфавіту та максимальну кількість вершин бору.
const int ALPH = 26;
const int MAXN = 500000 + 5;Масив зберігає переходи автомата, а — суфіксні посилання. Прапорець означає, що з вершини за суфіксними посиланнями досяжний кінець якогось зразка, а — що вершину уже відвідано під час обробки тексту. Змінна містить поточну кількість вершин; корінь — вершина .
int go_[MAXN][ALPH];
int link_[MAXN];
bool term[MAXN], vis[MAXN];
int sz = 1;Функція addString вставляє зразок у бор і повертає номер вершини, в якій він закінчується.
int addString(const string &s)
{
int v = 0;
for (char ch : s)
{
int c = ch - 'a';
if (!go_[v][c]) go_[v][c] = sz++;
v = go_[v][c];
}
term[v] = true;
return v;
}Функція buildAutomaton за допомогою обходу в ширину обчислює суфіксні посилання, добудовує переходи автомата й обчислює прапорці . Покладемо корінь бору в чергу.
void buildAutomaton()
{
queue<int> q;
q.push(0);Вилучимо вершину з черги. Вершина оброблена раніше, тому її прапорець уже остаточний, і прапорець доповнюється прапорцем \mathit{term}[\mathit{link\_}[v]].
while (!q.empty())
{
int v = q.front(); q.pop();
term[v] = term[v] || term[link_[v]];Переберемо всі символи . Якщо в борі існує перехід v \to u за символом , то суфіксне посилання вершини дорівнює \mathit{go\_}[\mathit{link\_}[v]][c] (для дітей кореня це корінь), і вершину додають у чергу.
for (int c = 0; c < ALPH; c++)
{
int u = go_[v][c];
if (u)
{
link_[u] = (v == 0) ? 0 : go_[link_[v]][c];
q.push(u);
}Якщо переходу в борі немає, його добудовують: з вершини за символом автомат переходить у ту саму вершину, що й з . З кореня відсутній перехід веде до кореня.
else
go_[v][c] = (v == 0) ? 0 : go_[link_[v]][c];
}
}
}Основна частина програми. Зчитаємо текст і кількість зразків .
cin >> text >> k;Зчитаємо зразки, вставимо їх у бор і збережемо номери їхніх кінцевих вершин у масиві .
vector<int> endNode(k);
string p;
for (int i = 0; i < k; i++)
{
cin >> p;
endNode[i] = addString(p);
}Побудуємо автомат Ахо — Корасік.
buildAutomaton();Пропустимо текст через автомат.
int v = 0;
for (char ch : text)
{
v = go_[v][ch - 'a'];Після кожного переходу пройдемо ланцюжком суфіксних посилань від поточної вершини і позначимо вершини. Проходження зупиняється, якщо на решті ланцюжка немає кінців зразків (\mathit{term}[u] = \textbf{\textit{false}}) або вершина уже позначена.
for (int u = v; term[u] && !vis[u]; u = link_[u])
vis[u] = true;
}Зразок зустрічається в тексті тоді й лише тоді, коли його кінцева вершина позначена.
for (int i = 0; i < k; i++)
cout << (vis[endNode[i]] ? "YES" : "NO") << '\n';