Cod sursa(job #2064559)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 12 noiembrie 2017 15:19:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

int const lenmax = (int) 2e6;

string x, y;
int pre[lenmax], sol[1005];

void buildPre() {
  int i = 0, j = 1;
  while(j < x.size()) {
    if(x[i] == x[j]) {
      pre[j] = pre[j - 1] + 1;
      ++ j;
      ++ i;
    } else {
      if(i == 0) {
        pre[j] = 0;
	   ++ j;
      } else {
        i = pre[i - 1];
      }
    }
  }
}

int main() {
  in >> x >> y;
  buildPre();

  int nsol = 0;

  int i = 0, j = 0;
  while(j < y.size()) {
    while(i < x.size() && x[i] == y[j]) {
      ++ i, ++ j;
    }
    if(i == 0) {
      ++ j;
    } else {
      if(i == x.size()) {
        if(nsol < 1000)
          sol[nsol] = j - x.size();
        nsol++;
      }
      i = pre[i - 1];
    }
  }


  out << nsol << '\n';
  for(int i = 0; i < min(nsol, 1000); i++)
    out << sol[i] <<" ";
  return 0;
}