Opis naivnog rešenja

Za sve moguće pomeraje \(s\) (\(0 \leq s \leq n - m + 1\)) proverimo da li važi \(P[1..m] = T[s+1..s+m]\). Proveru \(P[1..m] = T[s+1..s+m]\) možemo izvršiti u \(m\) koraka tako što uporedimo da li su svi karakteri \(P[i]\) i \(T[s+i]\) jednaki (\(1 \leq i \leq m\)). Ukoliko \(P[i] = T[s+i]\) za svako \(i=1 \ldots m\), znamo da \(P[1..m] = T[s+1..s+m]\), inače \(P[1..m] \neq T[s+1..s+m]\). Jasno je da nije potrebno upoređivati sve karaktere na svim pozicijama. Kada naiđemo na poziciju \(i\) za koju \(P[i] \neq T[s + i]\), pretragu možemo zaustaviti jer tada znamo da \(P[1..m] \neq T[s+1..s+m]\). Ipak vremenska složenost ove provere je \(O(m)\) u najgorem slučaju. Kako imamo ukupno \(n-m+1\) ovakvih provera, ukupna složenost algoritam je \(O((n - m + 1) m)\). Međutim, ovo složenost se dostiže samo kada \(T=a^n\) i \(P=a^m\).

Razmotrimo sada i prosečnu složenost algoritma. Neka je \(\Sigma_d = \{ 0, 1, \ldots, d-1 \}\) azbuka od \(d \geq 2\) slova. I neka je \(\Sigma_d^{*}\) skup svih mogućih konačnih niski nad azbukom \(\Sigma_d\). Neka su \(P\) i \(T\) proizvoljne niske iz \(\Sigma_d^{*}\). Izračunajmo prosečan broj upoređivanja pri proveri \(P[1..m]=T[s+1..s+m]\). Moramo uporediti karaktere \(P[1]\) i \(T[s+1]\). Karaktere \(P[2]\) i \(T[s + 2]\) upoređujemo samo ako \(P[1] = T[s+1]\). Dalje, karaktere \(P[3]\) i \(T[s+3]\) upoređujemo samo ako \(P[1] = T[s+1]\) i \(P[2] = T[s+2]\). Na kraju, karaktere \(P[m]\) i \(T[s+m]\) upoređujemo samo ako \(P[1] = T[s+1], T[2] = T[s+1], \ldots, P[m-1] = T[s+m-1]\). Zbog toga, može se pokazati da je broj upoređivanja za dati pomeraj \(s\):

\[1 + \frac{1}{d} + \frac{1}{d^2} + \ldots + \frac{1}{d^{m-1}} = \frac{1 - \frac{1}{d^m}}{1 - \frac{1}{d}}.\]

Kako je \(d \geq 2\), tada je \(1 - \frac{1}{d} \leq \frac{1}{2}\) i \(1 - \frac{1}{d^m} < 1\), te imamo da je

\[\frac{1 - \frac{1}{d^m}}{1 - \frac{1}{d}} \leq 2.\]

Zbog toga imamo najviše \(2(n-m+1)\) upoređivanja, te je prosečna složenost algoritma \(O(n)\).

#include <iostream>
#include <string>

using namespace std;

void naive_string_matcher(const string &text, const string &pattern)
{
    const int n = text.size();
    const int m = pattern.size();

    for (int s = 0; s < n - m + 1; s++) {
        // pattern[0..m-1] == text[s..s+m-1]?
        for (int i = 0; i < m; i++) {
            if (pattern[i] != text[s + i]) {
                break;
            } else if (i == m - 1){
                cout << s << ' ';
            }
        }
    }
    cout << endl;
}

int main(void)
{
    string text, pattern;
    cin >> text >> pattern;

    naive_string_matcher(text, pattern);
    
    return 0;
}

Opis glavnog rešenja

Za bolje rešenje iskoristićemo činjenicu da su svi karakteri niske \(P\) različiti, tj. za svako \(i, j = 1, \ldots, m\), ako je \(i \neq j\) tada je \(P[i] \neq P[j]\). Naime, ukoliko postoji neko \(j \in \{ 2, \ldots, m \}\) za koje \(P[j] \neq T[s+j]\) i za svako \(i = 1, \ldots, j - 1\) važi \(P[i] = T[s+i]\), tada znamo da će za svako \(i = 1, \ldots, j - 1\), \(P[1..j - i] \neq T[s+i..s+j-1]\), te će kandidat za sledeći validni pomeraj biti \(s + j - 1\). Specijalni slučaj nastaje kada \(j = 1\) ili \(j = m + 1\), i tada će kandidat za sledeći validni pomeraj biti \(s + 1\) ili \(s + m + 1\), respektivno.

Primetimo da sada za svako \(i = 1, \ldots, n\) imamo najviše dva poređenja sa karakterom \(T[i]\). Zbog toga, ukupno imamo najviše \(2n\) poređenja, te je složenost ovog algoritma \(O(n)\).

#include <iostream>
#include <string>

using namespace std;

void all_different_matcher(const string &text, const string &pattern)
{
    const int n = text.size();
    const int m = pattern.size();

    int s = 0;
    while (s < n - m + 1) {
        // pattern[0..m-1] == text[s..s+m-1] ?
        for (int i = 0; i < m; i++) {
            if (pattern[i] != text[s]) {
                if (i == 0) {
                    s += 1;
                }
                break;
            } else if (i == m - 1){
                cout << s - m + 1 << ' ';
            }
            s += 1;
        }
    }
    cout << endl;
}

int main(void)
{
    string text, pattern;
    cin >> text >> pattern;

    all_different_matcher(text, pattern);

    return 0;
}