Cod sursa(job #2105799)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 14 ianuarie 2018 12:04:11
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

void Solve (string s, int l) {
  
  int o = -1, r = -1, ans = 0, sz = (int) s.size ();
  vector < int > z (sz + 1), sol;

  for (int i = 2; i < sz; ++ i) {

    if (i >= r) {
      ++ z[i];
      while (i + z[i] - 1 < sz and s[i + z[i] - 1] == s[z[i]]) {
        ++ z[i];
      }

      -- z[i];
      o = i;
      r = i + z[i] - 1;
      if (z[i] == l) {
        ++ ans;
        sol.push_back (i - l - 2);
      }

      continue;
    }

    int k = z[i - o + 1];
    if (i + k - 1 <= r) {
      z[i] = k;
      if (z[i] == l) {
        ++ ans;
        sol.push_back (i - l - 2);
      }

      continue;
    }

    z[i] = r - i + 1;
    while (i + z[i] - 1 < sz and s[i + z[i] - 1] ==  s[z[i]]) {
      ++ z[i];
    }

    -- z[i];
    o = i;
    r = i + z[i] - 1;
    if (z[i] == l) {
      ++ ans;
      sol.push_back (i - l - 2);
    }
  }

  cout << ans << '\n';
  for (auto x : sol) {
    cout << x << ' ';
  }
  cout << '\n';
}

int main () {
  ios::sync_with_stdio (false);
  
  string s1, s2;
  cin >> s1 >> s2;
  s2 = ' ' + s1 + '#' + s2;
  
  Solve (s2, (int) s1.size ());
}