Nümunələrin tapılması#2603

Nümunələrin tapılması (Həll təhlili)

Şablonlar çoxluğu üçün Aho — Corasick avtomatını quraq. Şablonların ümumi uzunluğu 5 \cdot 10^5-dən çox olmadığından, trie ən çoxu 5 \cdot 10^5 + 1 təpədən ibarətdir. Əlifba kiçik latın hərfindən ibarətdir. Şablonun bitdiyi təpə terminal kimi işarələnir və hər şablonu üçün onun bitdiyi təpənin nömrəsini olaraq saxlayırıq. Eyni şablonlar eyni təpədə bitir.

Mətnin emalı. Mətni avtomatdan keçirək. Fərz edək ki, növbəti simvolu oxuduqdan sonra avtomat təpəsindədir. Onda sonluq keçidlərinin zənciri üzərindəki v \to \mathit{link}[v] \to \ldots \to 0 təpələri indiyədək oxunmuş mətnin şablonların prefiksi olan bütün sonluqlarına uyğun gəlir. Hər hansı şablon mətndə cari mövqedə bitməklə rast gəlinir ancaq və ancaq onun bitdiyi təpə bu zəncir üzərində yerləşdikdə. Deməli, sonluq keçidləri zəncirlərinin keçdiyi bütün təpələri bayrağı ilə işarələmək kifayətdir. şablonu üçün cavab qiymətidir.

Niyə bütün zənciri keçmək olmaz. Zəncirin uzunluğu şablonun uzunluğu tərtibində ola bilər. Məsələn, , , , şablonları və mətni üçün hər mövqedə uzun zənciri keçmək tələb olunardı və ümumi vaxt O(n \cdot L) olardı, burada — ən uzun şablonun uzunluğudur. Buna görə, zəncirin keçilməsi iki halda dayandırılır:

İkinci müddəa doğrudur, çünki təpəsi işarələndikdə keçid həmişə onun sonluq keçidi boyunca davam edir və yalnız \mathit{term} = \textbf{\textit{false}} olan təpədə və ya artıq işarələnmiş təpədə dayanır. Beləliklə, hər təpə ən çoxu bir dəfə işarələnir.

Mürəkkəblik. Avtomatın qurulması O(V \cdot 26) vaxt tələb edir, burada V \le 5 \cdot 10^5 + 1 — trie təpələrinin sayıdır. Mətnin emalı keçid plyus işarələmə tələb edir, cavablar isə vaxtında çap edilir. Keçid massivi təxminən 5 \cdot 10^5 \cdot 26 \cdot 4 bayt MB tutur.

Misal

Mətn -dur, şablonlar isə , , . Şablonları verilmiş ardıcıllıqla trie-ə əlavə edək. Təpə nömrələri onların yaradılma ardıcıllığına uyğundur, hər təpənin altında onun sətri yazılıb, terminal təpələr isə vurğulanıb: \mathit{endNode} = (3, 6, 9).

Kökə aparmayan sonluq keçidləri:

Heç bir sonluq keçidi terminal təpəyə aparmır, buna görə \mathit{term} = \textbf{\textit{true}} yalnız , və təpələrində doğrudur.

Mətni avtomatdan keçirək. Hər simvolun altında onu oxuduqdan sonra avtomatın düşdüyü təpə göstərilib.

char

təpənin sətri

işarələnmiş təpələr

0

4

—

1

7

—

2

8

—

3

9

9 ()

4

3

3 ()

5

0

—

6

0

—

indeksli simvoldan sonra avtomat terminal təpə olan -dadır (): bu təpə işarələnir və zəncirin keçilməsi \mathit{link}[9] = 2 təpəsində dayanır, çünki \mathit{term}[2] = \textbf{\textit{false}}. Növbəti simvol -dir: trie-də təpəsindən ilə keçid yoxdur, buna görə sonluq keçidi vasitəsilə avtomat \mathit{go}[2][b] = 3 () təpəsinə keçir, bu təpə də işarələnir. () təpəsi heç vaxt işarələnmir.

Cavab: \mathit{vis}[3] = \textbf{\textit{true}}, \mathit{vis}[6] = \textbf{\textit{false}}, \mathit{vis}[9] = \textbf{\textit{true}}, yəni YES, NO, YES.

Keçidin bayrağı ilə dayandırılması. , , şablonlarını və mətnini nəzərdən keçirək. Trie (), (), () təpələrindən ibarət zəncirdir, onların hamısı terminaldır, sonluq keçidləri isə 3 \to 2 \to 1 \to 0 istiqamətində aparır.

addım

zəncirin keçilməsi

işarələnib

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})

—

Hər təpə düz bir dəfə işarələnir. bayrağı olmasaydı, ikinci addımdan başlayaraq hər dəfə zənciri yenidən kökə qədər keçmək lazım gələrdi.

Alqoritmin Reallaşdırılması

Sabitləri elan edək: əlifbanın ölçüsü və trie təpələrinin maksimum sayı.

const int ALPH = 26;
const int MAXN = 500000 + 5;

massivi avtomatın keçidlərini, isə sonluq keçidlərini saxlayır. bayrağı təpəsindən sonluq keçidləri vasitəsilə şablon sonuna çatıla biləcəyini bildirir, isə mətni emal edərkən təpəsinin artıq ziyarət edildiyini bildirir. dəyişəni cari təpələrin sayını saxlayır; kök təpə -dır.

int go_[MAXN][ALPH];
int link_[MAXN];
bool term[MAXN], vis[MAXN];
int sz = 1;

addString funksiyası şablonunu trie-ə əlavə edir və onun bitdiyi təpənin nömrəsini qaytarır.

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 funksiyası eninə axtarış istifadə edərək sonluq keçidlərini hesablayır, avtomatın keçidlərini tamamlayır və bayraqlarını hesablayır. Trie-nin kökünü növbəyə əlavə edək.

void buildAutomaton()
{
  queue<int> q;
  q.push(0);

Növbədən təpəsini çıxaraq. təpəsi daha əvvəl emal edildiyindən onun bayrağı artıq sondur, buna görə bayrağı \mathit{term}[\mathit{link\_}[v]] bayrağı ilə tamamlanır.

  while (!q.empty())
  {
    int v = q.front(); q.pop();
    term[v] = term[v] || term[link_[v]];

Bütün simvolları üzrə dövr edək. Əgər trie-də v \to u keçidi simvolu ilə mövcuddursa, onda təpəsinin sonluq keçidi \mathit{go\_}[\mathit{link\_}[v]][c]-ə bərabərdir (kökün uşaqları üçün bu kökdür), və təpəsi növbəyə əlavə edilir.

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

Əgər trie-də keçid yoxdursa, o tamamlanır: təpəsindən simvolu ilə avtomat -dən olduğu kimi eyni təpəyə keçir. Kökdən çatışmayan keçid kökə aparır.

      else
        go_[v][c] = (v == 0) ? 0 : go_[link_[v]][c];
    }
  }
}

Proqramın əsas hissəsi. Mətni və şablonların sayı -nı oxuyaq.

cin >> text >> k;

Şablonları oxuyaq, onları trie-ə əlavə edək və onların bitdiyi təpələrin nömrələrini massivində saxlayaq.

vector<int> endNode(k);
string p;
for (int i = 0; i < k; i++)
{
  cin >> p;
  endNode[i] = addString(p);
}

Aho — Corasick avtomatını quraq.

buildAutomaton();

Mətni avtomatdan keçirək.

int v = 0;
for (char ch : text)
{
  v = go_[v][ch - 'a'];

Hər keçiddən sonra cari təpəsindən sonluq keçidləri zənciri boyunca gedib təpələri işarələyək. Keçid, əgər zəncirin qalan hissəsində şablon sonları yoxdursa (\mathit{term}[u] = \textbf{\textit{false}}) və ya təpəsi artıq işarələnibsə, dayandırılır.

  for (int u = v; term[u] && !vis[u]; u = link_[u])
    vis[u] = true;
}

şablonu mətndə rast gəlinir ancaq və ancaq onun bitdiyi təpə işarələnibsə.

for (int i = 0; i < k; i++)
  cout << (vis[endNode[i]] ? "YES" : "NO") << '\n';