Şablonlar çoxluğunun tapılması 1#2171

Şablonlar çoxluğunun tapılması 1 (Həll təhlili)

Əgər çoxluğunun hər bir sətri üçün hər bir nümunəni ayrıca axtarsaq, onda ümumi giriş ölçüsü MB-a qədər və nümunə olduqda çox sayda əməliyyat olacaq. Gəlin çoxluğu üçün Aho — Corasick avtomatını qurub, -in hər bir sətrini onun simvolları üzərində bir dəfə keçməklə yoxlayaq.

Trie (ön şəkilçi ağacı). Bütün nümunələri trie-ə əlavə edək. Sətirlər kodları -dən -ya qədər olan ASCII simvollarından ibarətdir, buna görə də keçidlər simvolun kodu ilə birbaşa indeksləşdirilən ölçülü massivdə saxlanılır. Ən çoxu nümunə var, hər birinin uzunluğu ən çoxu -dir; deməli, trie ən çoxu 100 \cdot 80 + 1 təpədən ibarətdir. Nümunənin bitdiyi təpə terminal kimi işarələnir.

Avtomat. Enlik üzrə axtarışdan (BFS) istifadə edərək, suffiks keçidlərini hesablayırıq və avtomatın keçidlərini tamamlayırıq: \mathit{go}[v][c] — təpəsindən simvolu ilə avtomatın keçdiyi təpədir. Bundan sonra hər bir təpənin istənilən simvol üzrə keçidi olur və sətri emal edərkən suffiks keçidlərini izləməyə ehtiyac qalmır.

bayrağı. Avtomat tərəfindən indiyədək oxunmuş sətir hansısa nümunə ilə bitir, əgər və yalnız əgər cari təpədən suffiks keçidləri zənciri boyunca hansısa terminal təpəyə çatmaq mümkündürsə. Buna görə də hər bir təpə üçün aşağıdakı bayrağı hesablayırıq:

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

Təpələr enlik üzrə axtarış sırasında emal edilir, və təpəsi -dən köküə daha yaxındır, ona görə emal olunana qədər \mathit{term}[\mathit{link}[v]] qiyməti artıq sonuncu qiymətdir.

Sətrin yoxlanması. -in növbəti sətri üçün kökdən başlayırıq və onun simvolları boyunca hərəkət edirik. Əgər hansısa keçiddən sonra \mathit{term}[v] = \textbf{\textit{true}} olan təpədəyiksə, onda oxunmuş sətrin prefiksi hansısa nümunə ilə bitir, yəni sətir alt sətir kimi nümunə saxlayır. Qalan simvolları oxumağa ehtiyac yoxdur: sətir çap olunur. Əgər sətir sona qədər oxunub və bayraq heç vaxt qarşılaşılmayıbsa, o, heç bir nümunə saxlamır.

Giriş. çoxluğunun sətirləri boşluqlar saxlaya bilər, buna görə onlar getline funksiyası ilə oxunur. ədədini oxuduqdan sonra, ilk sətrin qalan hissəsi oxunmalıdır. Boş sətir boş olmayan nümunə saxlaya bilməz, buna görə o heç vaxt çap edilmir.

Mürəkkəblik. Avtomatın qurulması O(V \cdot 128) vaxt tələb edir, burada V \le 8001 trie təpələrinin sayıdır. -in hər bir sətri onun uzunluğuna mütənasib vaxtda emal olunur, buna görə bütün axtarış vaxtında işləyir, burada girişin ümumi ölçüsüdür. Keçid massivi təxminən 8001 \cdot 128 \cdot 4 bayt MB tutur.

Misal

Nümunələr çoxluğu T = \{abc, bca, aba, bcc, aac\} olsun. Nümunələri verilmiş sırada trie-ə əlavə edək. Təpə nömrələri onların yaradılma sırasına uyğundur; hər təpənin altında ona uyğun sətir yazılıb. Terminal təpələr vurğulanıb, və nümunə onların yanında göstərilib.

Suffiks keçidlərini hesablayaq. Təpənin suffiks keçidi onun sətrinin trie-də mövcud olan ən uzun xüsusi suffiksinə uyğun təpəyə aparır:

Heç bir suffiks keçidi terminal təpəyə aparmır, buna görə bayraqları nümunə uclarının işarələri ilə üst-üstə düşür: \mathit{term} = \textbf{\textit{true}} yalnız , , , və təpələrində.

Cədvəldə suffiks keçidləri, bayraqları və avtomatın , , simvolları üzrə keçidləri göstərilib. Trie-də olmayan keçidlər suffiks keçidlərindən istifadə etməklə tamamlanır. Bütün digər simvollar üzrə avtomat istənilən təpədən kökə keçir.

sətir

\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

Məsələn, trie-də () təpəsindən simvolu ilə keçid yoxdur. Avtomat \mathit{link}[9] = 1 () təpəsindən keçidi götürür: \mathit{go}[9][b] = \mathit{go}[1][b] = 2. Doğrudan da, oxunduqdan sonra, hansısa nümunənin prefiksi olan ən uzun suffiks -dir.

Gəlin çoxluğunun sətirlərini avtomatdan keçirək. Hər simvolun altında onu oxuduqdan sonra avtomatın hansı təpədə olduğu göstərilib.

Cavab və sətirlərindən ibarətdir.

Alqoritmin Reallaşdırılması

Sabitləri elan edək. Avtomatın əlifbası simvoldan ibarətdir, və simvol kodları indeks kimi istifadə olunur. Trie təpələrinin maksimum sayı 100 \cdot 80 üstəgəl kiçik ehtiyat.

const int ALPH = 128;               // ASCII codes 32..126
const int MAXN = 100 * 80 + 5;      // maximum number of trie vertices

massivi avtomatın keçidlərini saxlayır, suffiks keçidlərini saxlayır, və — təpəsindən suffiks keçidləri vasitəsilə nümunənin sonuna çatmağın mümkün olduğunu göstərən bayraqdır. dəyişəni cari təpələrin sayını saxlayır; kök təpəsidir. Qlobal massivlər başlanğıcda sıfırlarla doldurulur, buna görə trie-də \mathit{go\_}[v][c]-nın sıfır qiyməti keçidin olmadığını bildirir.

int go_[MAXN][ALPH];   // transitions of the automaton
int link_[MAXN];       // suffix links
bool term[MAXN];       // the end of a pattern is reachable
                       // from the vertex via suffix links
int sz = 1;            // number of vertices, 0 is the root

addString funksiyası nümunəsini trie-ə əlavə edir. Simvol kodunun qeyri-mənfi indeks kimi istifadə edilməsi üçün o unsigned char kimi qəbul edilir. Əgər simvol üzrə keçid yoxdursa, yeni təpə yaradılır. Nümunənin bitdiyi təpədə bayrağı təyin edilir.

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 funksiyası enlik üzrə axtarış vasitəsilə suffiks keçidlərini hesablayır və avtomatın keçidlərini tamamlayır.

void buildAutomaton()
{
  queue<int> q;

Trie-in kökünü (0 nömrəli təpəni) növbəyə əlavə edək. Enlik üzrə axtarış ondan başlayır.

  q.push(0);

Növbədən təpəsini çıxaraq. Onun suffiks keçidi artıq hesablanıb, və təpəsi daha əvvəl emal edilib, buna görə bayrağı dərhal təpəsinin bayrağı ilə tamamlana bilər.

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

Bütün simvolları üzərindən keçək. Əgər trie-də v \to u keçidi simvolu üzrə varsa, onda təpəsinin suffiks 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. Nümunələrin sayı -i oxuyun, sonra isə getline funksiyasından istifadə edərək ədədini ehtiva edən sətrin qalan hissəsini oxuyun.

cin >> n;
getline(cin, line);       // read the rest of the line with the number n

Nümunələri oxuyun və boş olmayanları trie-ə əlavə edin.

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

Aho — Corasick avtomatını qurun.

buildAutomaton();

çoxluğunun sətirlərini girişin sonuna qədər oxuyun. Hər bir sətir üçün kökdən başlayırıq; bayrağı onda nümunənin tapılıb-tapılmadığını göstərir.

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

Sətrin simvollarından keçin. Kodları və daha çox olan simvollar avtomatda təmsil olunmur (şərtə görə, onlar girişdə rast gəlinmir); əgər onlar görünsə, avtomat kökə qayıdır. Avtomat bayraqlı təpəyə çatan kimi, sətir nümunə saxlayır, və sətrin skanlanması dayandırılır.

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

Əgər nümunə tapılıbsa, sətri çap edin.

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