KMP#1498

KMP (Həll təhlili)

Bu məsələdə Knut-Morris-Pratt mətn axtarış alqoritmi tətbiq edilməlidir.

Alqoritmin Tətbiqi

Aşağıdakı dəyişənləri elan edək:

$t e x t$ — burada $w or d$ şablonun bütün uyğunluqları tapılmalı olan sətirdir.
$w or d$ — $t e x t$ sətrində axtarılan alt sıra (şablon).
$p$ — $w or d$ sətrinin prefiks-funksiya dəyərlərini saxlayan massiv.
$p os$ — $t e x t$ sətrində $w or d$ alt sətrinin uyğunluqla başladığı bütün mövqelərin siyahısı.

string text, word;
vector<int> p, pos;

MaxBorderArray funksiyası $s$ sətrinin prefiks-funksiya dəyərlərini hesablayır və onları $p$ massivinə saxlayır.

void MaxBorderArray(string &s)
{
  p.resize(s.size());
  for (int i = 1; i < s.size(); i++)
  {
    int j = p[i - 1];
    while ((j > 0) && (s[i] != s[j])) j = p[j - 1];
    if (s[i] == s[j]) j++;
    p[i] = j;
  }
}

C++

Kmp funksiyası Knut — Morris — Pratt alqoritmini həyata keçirir. $w or d$ sətrinin $t e x t$ sətrindəki bütün başlanğıc indeksləri $p os$ massivinə yazılır.

void kmp(string &word, string &text)
{
  MaxBorderArray(word);
  for (int i = 0, j = 0; i < text.size(); i++)
  {
    while (j && (text[i] != word[j])) j = p[j - 1];
    if (text[i] == word[j]) j++;

C++

Əgər $j$ indeksinin dəyəri $w or d$ sətrinin son işarəsinə çatırsa, bu, $w or d$ sözünün tam uyğunluğunun mətndə tapıldığı deməkdir. Tətbiq olunan uyğunluğun başlanğıc mövqeyi $i - j + 1$ i - j + 1-dir (işarələrin nömrələnməsi sıfırdan başlayır).

    if (j == word.size()) pos.push_back(i - j + 1);
  }
}

Proqramın əsas hissəsi. Giriş sətirlərini oxuyuruq.

cin >> text;
cin >> word;

Knut-Morris-Pratt alqoritmini işə salırıq.

kmp(word, text);

Tapılan uyğunluq mövqelərini çıxarırıq.

for (auto x : pos)
  cout << x << " ";
cout << endl;