Naxışların sayılması#2604

Naxışların sayılması (Həll təhlili)

Nümunələrin çoxluğu üçün Aho — Corasick avtomatını quraq. Nümunələrin ümumi uzunluğu 5 \cdot 10^5-dən çox deyil, ona görə də trie ən çoxu 5 \cdot 10^5 + 1 təpədən ibarətdir, əlifba isə kiçik latın hərfindən ibarətdir. Hər bir nümunəsi üçün onun bitdiyi təpənin nömrəsini saxlayırıq. Eyni nümunələr eyni təpədə bitir.

Mətnin emal edilməsi. Mətni avtomat üzərindən keçirək. Növbəti hərfi oxuduqdan sonra avtomat indiyədək oxunmuş mətnin ən uzun suffiksinə uyğun gələn, həmçinin hansısa nümunənin prefiksi olan təpəsində olur. sayğacını artırırıq. Nəticədə mətnin neçə mövqeyində avtomatın təpəsində olduğuna bərabərdir.

Dəfələrin sayılması. nümunəsi cari mətn mövqeyində bitir, əgər və yalnız əgər təpəsi v \to \mathit{link}[v] \to \ldots \to 0 suffiks keçidləri zəncirində yerləşirsə. Başqa sözlə, təpəsi, avtomatın suffiks keçid ağacında (bu ağacda təpəsinin valideyni -dir) onun alt ağacının təpələrində olduğu bütün mövqelərdə "sayılır". Deməli, təpəsinin sətrinin neçə dəfə rast gəldiyi, təpəsinin alt ağacı üzrə -lərin cəminə bərabərdir.

Mətnin hər hərfindən sonra keçidlər zəncirini izləmək icazəli deyil: zəncirlər uzun ola bilər. Bunun əvəzinə alt ağac cəmlərini sonda bir dəfə hesablayırıq. Suffiks keçidi daha kiçik dərinlikli təpəyə aparır, en üzrə axtarış isə təpələri qeyri-azalan dərinlik ardıcıllığında gəzir. Deməli, əgər təpələri en üzrə axtarışın tərs ardıcıllığında gəzsək və hər bir təpəsi üçün \mathit{cnt}[\mathit{link}[u]] \mathrel{+}= \mathit{cnt}[u] əməliyyatını yerinə yetirsək, onda təpə emal olunana qədər onun sayğacı artıq bütün alt ağacı üzrə cəmi saxlayacaq.

nümunəsi üçün cavab -ə bərabərdir.

Mürəkkəblik. Avtomatın qurulması O(V \cdot 26) vaxt tələb edir, burada — trie təpələrinin sayıdır, mətnin emalı , sayğacların yığılması , cavabların çap edilməsi isə vaxt alır. Keçid massivi təxminən 5 \cdot 10^5 \cdot 26 \cdot 4 bayt MB tutur.

Misal

Mətn -dir, nümunələr isə , , , -dir. Nümunələri verilmiş sırayla trie-ə əlavə edək. Təpələrin nömrələri onların yaradılma sırasına uyğundur, terminal təpələr isə işıqlandırılıb: \mathit{endNode} = (2, 4, 6, 7).

Suffiks keçidləri: \mathit{link}[2] = 5 (ab \to b), \mathit{link}[3] = 7 (ac \to c), \mathit{link}[4] = 5 (acb \to b), \mathit{link}[6] = 1 (ba \to a). , , təpələrinin keçidləri kökə aparır. En üzrə axtarış təpələri 0, 1, 5, 7, 2, 3, 6, 4 sırasında gəzir.

Mətni avtomat üzərindən keçirək. Hər hərfin altında, onu oxuduqdan sonra avtomatın hansı təpəsinə gəldiyi göstərilib.

Məsələn, oxunduqdan sonra (-cü mövqe) avtomat () təpəsindədir. nümunəsi də bu mövqedə bitir, lakin avtomat onun təpəsi olan -də deyil, -cü təpədədir, oradan isə suffiks keçidi -ci təpəyə aparır. Məhz buna görə də sayğacları suffiks keçid ağacı üzrə yığmaq lazımdır.

0, \ldots, 7 təpələri üçün ziyarət sayları \mathit{cnt} = (0, 2, 3, 1, 0, 1, 2, 2)-dir. Təpələri 4, 6, 3, 2, 7, 5, 1 tərs en üzrə axtarış sırasında gəzib hər bir təpənin sayğacını onun suffiks keçidinin sayğacına əlavə edirik. Şəkildə suffiks keçid ağacı göstərilib; hər bir təpə üçün ziyarət sayı və onun alt ağacı üzrə yekun cəm verilib.

Cavablar: \mathit{cnt}[2] = 3 (), \mathit{cnt}[4] = 0 (), \mathit{cnt}[6] = 2 (), \mathit{cnt}[7] = 1 + 2 = 3 ().

Alqoritmin Reallaşdırılması

Sabitləri və işçi massivləri elan edək. massivi avtomatın keçidlərini, suffiks keçidlərini, isə təpəsinin ziyarət sayını (yığım əməliyyatından sonra isə onun sətrinin mətndə neçə dəfə rast gəldiyini) saxlayır. dəyişəni cari təpələrin sayını saxlayır; kök nömrəli təpədir. vektoru təpələrin en üzrə axtarış sırasını saxlayır.

#define ALPH 26
#define MAXN 500005
int go_[MAXN][ALPH];
int link_[MAXN];
int cnt[MAXN];
int sz = 1;
vector<int> order;

addString funksiyası nümunəsini 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];
  }
  return v;
}

buildAutomaton funksiyası en üzrə axtarışdan istifadə edərək suffiks keçidlərini hesablayır və avtomatın keçidlərini tamamlayır.

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

Növbədən çıxarılan hər bir təpə vektoruna əlavə edilir.

    int v = q.front(); q.pop();
    order.push_back(v);

Əgər trie-də hərfi ilə v \to u keçidi varsa, onda təpəsinin suffiks keçidi \mathit{go\_}[\mathit{link\_}[v]][c]-yə bərabərdir (kökün uşaqları üçün isə bu kökə bərabərdir), və təpəsi növbəyə əlavə edilir. Əks halda keçid tamamlanır: təpəsindən hərfi ilə avtomat -dən olduğu kimi eyni təpəyə keçir.

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

Proqramın əsas hissəsi. Mətni və nümunələrin sayı -nı oxuyaq.

cin >> text >> k;

Nümunələri oxuyaq, onları trie-ə əlavə edək və onların son təpələrinin 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 avtomat üzərindən keçirək və avtomatın hər bir təpəni neçə dəfə ziyarət etdiyini sayaq.

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

Təpələri tərs en üzrə axtarış sırasında (kök istisna olmaqla) gəzək və təpəsinin sayğacını onun suffiks keçidinin sayğacına əlavə edək. Bundan sonra , təpəsinin suffiks keçid ağacındakı alt ağacı üzrə ziyarətlərin cəminə bərabər olacaq.

for (int i = (int)order.size() - 1; i > 0; i--)
{
  int u = order[i];
  cnt[link_[u]] += cnt[u];
}

nümunəsinin mətndə rast gəlmə sayı onun son təpəsinin sayğacına bərabərdir.

for (int i = 0; i < k; i++)
  cout << cnt[endNode[i]] << '\n';