Пошук шаблонів#2603

Пошук шаблонів (Розбір)

Побудуємо автомат Ахо — Корасік для множини зразків. Сумарна довжина зразків не перевищує 5 \cdot 10^5, тому бор містить не більше 5 \cdot 10^5 + 1 вершин. Алфавіт складається з малих латинських літер. Вершину, в якій закінчується зразок, позначимо як термінальну, а для кожного зразка зберігатимемо номер його кінцевої вершини . Однакові зразки закінчуються в одній і тій самій вершині.

Обробка тексту. Пропустимо текст через автомат. Нехай після зчитування чергового символу автомат перебуває у вершині . Тоді вершини на ланцюжку суфіксних посилань v \to \mathit{link}[v] \to \ldots \to 0 відповідають усім суфіксам уже зчитаного тексту, які є префіксами зразків. Зразок зустрічається в тексті та закінчується на поточній позиції тоді й лише тоді, коли його кінцева вершина лежить на цьому ланцюжку. Отже, достатньо позначити прапорцем усі вершини, через які проходять ланцюжки суфіксних посилань. Відповідь для зразка — це значення .

Чому не можна проходити весь ланцюжок. Довжина ланцюжка може бути порядку довжини зразка. Наприклад, для зразків , , , і тексту на кожній позиції довелося б проходити довгий ланцюжок, і сумарний час був би O(n \cdot L), де — довжина найдовшого зразка. Тому проходження ланцюжка зупиняється у двох випадках:

Друге твердження справедливе, оскільки при позначенні вершини проходження завжди продовжується вздовж її суфіксного посилання і зупиняється лише у вершині з \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{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';