Cirkularna niska

Neka je data niska \(S[1..n]\). Kažemo da je ona cirkularna ako važi da nakon \(S[n]\) ne dolazi kraj niske, već karakter \(S[1]\). Potrebno je pronaći sve indekse početka niske \(T[1..m]\) u cirkularnoj niski \(S[1..n]\).

Opis ulaza

Sa standardnog ulaza unose se niske \(S[1..n]\) i \(T[1..m]\) redom (\(1 \leq n, m \leq 10^5\)).

Opis izlaza

Na standardni izlaz ispisati sve početne indekse niske \(T[1..m]\) u cirkularnoj niski \(S[1..n]\), uređene rastuće. U slučaju da ne postoji ni jedan takav indeks, ispisati \(-1\).

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void compute_preffix_table(string &pattern, vector<int> &preffix_table)
{
    int n = pattern.size();

    preffix_table[0] = 0;

    int i = 1, j = 0;

    while (i < n) {
        if (pattern[i] == pattern[j]) {
            preffix_table[i] = j + 1;
            i++;
            j++;
        }
        else {
            if (j != 0) {
                j = preffix_table[j - 1];
            }
            else {
                preffix_table[i] = 0;
                i++;
            }
        }
    }
}

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

    vector<int> preffix_table(n);

    compute_preffix_table(pattern, preffix_table);

    int i = 0, j = 0;
    bool found = false;

    while ( (n - i) >= (m - j)) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }

        if (j == m) {
            if(i - j < text_len)
                cout << i - j << " ";
            j = preffix_table[j - 1];
            found = true;
            continue;
        }

        if (i < n && pattern[j] != text[i]) {
            if (j != 0)
                j = preffix_table[j - 1];
            else
                i++;
        }
    }

    if(!found) {
        cout << -1 << endl;
    }
}

int main ()
{
    string s, t;
    cin >> s >> t;

    string c = s + s;

    while(c.size() < s.size() + t.size() - 1){
        c += s;
    }

    kmp(c, t, s.size());

    return 0;
}