Cod sursa(job #2040396)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 15 octombrie 2017 19:11:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

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

void solve(string &s, int len, vector < int > &Z) {

  int index = 0;
  int L = -1, R = -1;
  vector < int > poz(1001);
  Z[0] = len;
  for (int i = 1; i < s.size(); i ++) {
    if (i >= R) {
      int cnt = 1;
      while (s[i + cnt - 1] == s[cnt - 1]) {
        cnt ++;
        if (i + cnt - 1 > s.size()) {
          break;
        }
      }

      cnt --;
      L = i;
      Z[i] = cnt;
      R = i + cnt - 1;
    }

    int k = Z[i - L];
    if (i + k - 1 < R) {
      Z[i] = k;
      continue;
    }

    int cnt = R - i + 1;
    while (s[i + cnt - 1] == s[cnt - 1]) {
      cnt ++;
      if (i + cnt - 1 > s.size()) {
        break;
      }
    }

    cnt --;
    L = i;
    Z[i] = cnt;
    R = i + cnt - 1;
  }

  int sol = 0;
  for (int i = len + 1; i < s.size(); i ++) {
    if (Z[i] == len) {
      sol ++;
      if (index < 1000) {
        poz[++ index] = i - len - 1;
      }
    }
  }

  cout << sol << '\n';
  for (int i = 1; i <= index; i ++) {
    cout << poz[i] << ' ';
  }
  cout << '\n';
}

int main(int argc, char const *argv[]) {
  
  string pattern;
  string s;
  cin >> pattern >> s;

  s = pattern + '#' + s;

  vector < int > Z(s.size() + 7);
  solve(s, pattern.size(), Z);
}