Знайти набір шаблонів 1#2171

Знайти набір шаблонів 1 (Розбір)

Якщо для кожного рядка множини шукати кожен шаблон окремо, то при сумарному розмірі вхідних даних до МБ і шаблонах операцій буде занадто багато. Побудуємо автомат Ахо — Корасік для множини і перевіримо кожен рядок множини за один прохід по його символах.

Бор. Додамо всі шаблони в бор. Рядки складаються із символів ASCII з кодами від до , тому переходи зберігаються в масиві розміром , індексованому безпосередньо кодом символу. Шаблонів не більше , кожен довжиною не більше ; отже, бор містить не більше 100 \cdot 80 + 1 вершин. Вершина, у якій закінчується шаблон, позначається як термінальна.

Автомат. За допомогою обходу в ширину обчислимо суфіксні посилання та доповнимо переходи автомата: \mathit{go}[v][c] — вершина, до якої автомат переходить з за символом . Після цього з кожної вершини є перехід за будь-яким символом, і під час обробки рядка немає потреби йти суфіксними посиланнями.

Прапорець . Прочитаний автоматом на даний момент рядок закінчується якимось шаблоном тоді й лише тоді, коли з поточної вершини по ланцюжку суфіксних посилань досяжна термінальна вершина. Тому для кожної вершини обчислюємо прапорець

\mathit{term}[v] = \mathit{term}[v] \lor \mathit{term}[\mathit{link}[v]]

Вершини обробляються в порядку обходу в ширину, а вершина знаходиться ближче до кореня, ніж , тому на момент обробки значення \mathit{term}[\mathit{link}[v]] вже остаточне.

Перевірка рядка. Для чергового рядка множини почнемо з кореня і будемо переходити за його символами. Якщо після якогось переходу ми опинилися у вершині з \mathit{term}[v] = \textbf{\textit{true}}, то щойно прочитаний префікс рядка закінчується якимось шаблоном, тобто рядок містить шаблон як підрядок. Решту символів читати не потрібно: рядок виводиться. Якщо рядок прочитано до кінця, а прапорець так і не спрацював, він не містить жодного шаблону.

Вхідні дані. Рядки множини можуть містити пробіли, тому вони читаються за допомогою функції getline. Після зчитування числа потрібно зчитати залишок першого рядка. Порожній рядок не може містити непорожній шаблон, тому він ніколи не виводиться.

Складність. Побудова автомата займає O(V \cdot 128), де V \le 8001 — кількість вершин бору. Кожен рядок множини обробляється за час, пропорційний його довжині, тому весь пошук виконується за , де — сумарний розмір вхідних даних. Масив переходів займає близько 8001 \cdot 128 \cdot 4 байтів МБ.

Приклад

Множина шаблонів T = \{abc, bca, aba, bcc, aac\}. Додамо шаблони в бор у заданому порядку. Номери вершин відповідають порядку їх створення; під кожною вершиною записано рядок, якому вона відповідає. Термінальні вершини виділено, а поруч із ними вказано шаблон.

Обчислимо суфіксні посилання. Суфіксне посилання вершини веде до вершини, що відповідає найдовшому власному суфіксу її рядка, який присутній у борі:

Жодне суфіксне посилання не веде до термінальної вершини, тому прапорці збігаються з позначеннями кінців шаблонів: \mathit{term} = \textbf{\textit{true}} лише у вершинах , , , і .

У таблиці наведено суфіксні посилання, прапорці і переходи автомата за символами , , . Переходи, відсутні в борі, доповнено за допомогою суфіксних посилань. За всіма іншими символами автомат переходить з будь-якої вершини до кореня.

рядок

\boldsymbol{\mathit{go}['a']}

\boldsymbol{\mathit{go}['b']}

\boldsymbol{\mathit{go}['c']}

0

0

false

1

4

0

1

0

false

9

2

0

2

4

false

7

4

3

3

5

true

6

4

8

4

0

false

1

4

5

5

0

false

6

4

8

6

1

true

9

2

0

7

1

true

9

2

0

8

0

true

1

4

0

9

1

false

9

2

10

10

0

true

1

4

0

Наприклад, у борі немає переходу з вершини () за символом . Автомат виконує перехід з вершини \mathit{link}[9] = 1 (): \mathit{go}[9][b] = \mathit{go}[1][b] = 2. Дійсно, після зчитування найдовший суфікс, що є префіксом якогось шаблону, — це .

Пропустимо рядки множини через автомат. Під кожним символом показано вершину, у якій опиняється автомат після його зчитування.

Відповідь складається з рядків і .

Реалізація алгоритму

Оголосимо константи. Алфавіт автомата складається з символів, і коди символів слугують індексами. Максимальна кількість вершин бору — 100 \cdot 80 плюс невеликий запас.

const int ALPH = 128;               // коди ASCII 32..126
const int MAXN = 100 * 80 + 5;      // максимальна кількість вершин бору

Масив зберігає переходи автомата, — суфіксні посилання, а — прапорець того, що кінець шаблону досяжний з вершини через суфіксні посилання. Змінна містить поточну кількість вершин; корінь — вершина . Глобальні масиви спочатку заповнені нулями, тому нульове значення \mathit{go\_}[v][c] у борі означає відсутність переходу.

int go_[MAXN][ALPH];   // переходи автомата
int link_[MAXN];       // суфіксні посилання
bool term[MAXN];       // кінець шаблону досяжний
                       // з вершини через суфіксні посилання
int sz = 1;            // кількість вершин, 0 --- корінь

Функція addString додає шаблон у бір. Символ розглядається як unsigned char, щоб його код використовувався як невід'ємний індекс. Якщо переходу за символом немає, створюється нова вершина. У вершині, де закінчується шаблон, встановлюється прапорець .

void addString(const string &s)
{
  int v = 0;
  for (unsigned char c : s)
  {
    if (!go_[v][c]) go_[v][c] = sz++;
    v = go_[v][c];
  }
  term[v] = true;
}

Функція buildAutomaton обчислює суфіксні посилання та доповнює переходи автомата за допомогою обходу в ширину.

void buildAutomaton()
{
  queue<int> q;

Помістимо в чергу корінь бору (вершину номер ). З неї починається обхід у ширину.

  q.push(0);

Вилучимо вершину із черги. Її суфіксне посилання вже обчислено, а вершина оброблена раніше, тому прапорець можна одразу доповнити прапорцем вершини .

  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];
    }
  }
}

Основна частина програми. Зчитаємо кількість шаблонів , а потім за допомогою функції getline зчитаємо залишок рядка, що містить .

cin >> n;
getline(cin, line);       // зчитати залишок рядка з числом n

Зчитаємо шаблони та додамо непорожні в бір.

for (int i = 0; i < n; i++)
{
  getline(cin, line);
  if (!line.empty()) addString(line);
}

Побудуємо автомат Ахо — Корасік.

buildAutomaton();

Зчитуємо рядки множини до кінця вхідних даних. Для кожного рядка починаємо з кореня; прапорець показує, чи знайдено в ньому шаблон.

while (getline(cin, line))
{
  int v = 0;
  bool found = false;

Пройдемо по символах рядка. Символи з кодами і вище не представлені в автоматі (за умовою, вони не зустрічаються у вхідних даних); якщо вони з'являються, автомат повертається до кореня. Щойно автомат досягає вершини з прапорцем , рядок містить шаблон, і сканування рядка припиняється.

  for (unsigned char c : line)
  {
    v = go_[v][c];
    if (term[v]) { found = true; break; }
  }

Якщо шаблон знайдено, виводимо рядок.

  if (found) cout << line << '\n';
}