Cod sursa(job #1623987)

Utilizator pickleVictor Andrei pickle Data 1 martie 2016 23:18:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <string>

using namespace std;

const int Nmax = 2000666;
string A, B;

int M[Nmax];
int ans[1024], N = 0;

void computeMatch() {
  M[0] = -1;
  for(int k = 0; k+1 < A.size(); ++k) {
    int i = M[k];

    while(i >= 0) {
      if (A[k+1] == A[i+1]) {
        M[k+1] = i+1;
        break;
      }
      i = M[i];
    }
    if (i == -1) {
      if (A[k+1] == A[0])
        M[k+1] = 0;
      else
        M[k+1] = -1;
    }
  }
}

int main() {
  ifstream fin ("strmatch.in");
  ofstream fout ("strmatch.out");

  fin >> A >> B;
  computeMatch();
  int i = -1;
  for(int k = 0; k < B.size(); ++k) {
    while(i >= 0) {
      if (B[k] == A[i+1]) {
        ++i;
        break;
      }
      i = M[i];
    }
    if (i == -1 && B[k] == A[0]) {
      ++i;
    }

    if (i == A.size() - 1) {
      if (N < 1000)
        ans[N] = k - i;
      ++N;
      i = M[i];
    }
  }

  fout << N << endl;
  for (int i = 0; i < N && i < 1000; ++i) {
    fout << ans[i] << ' ';
  }
  fout << endl;

  return 0;
}