cirkularna

Neka je data niska \(s\) dužine \(N\). Kažemo da je ona cirkularna ako važi da nakon \(s[N-1]\) ne dolazi kraj niske, već karakter \(s[0]\). Potrebno je pronaći sve indekse početka niske \(t\) u cirkularnoj niski \(s\).

Opis ulaza

Opis izlaza

Na standardni izlaz ispisati sve početne indekse niske \(t\) u cirkularnoj niski \(s\), 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();

 std::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)
         std::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)
      std::cout << -1;
}

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

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

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

  return 0;
}