Cod sursa(job #1522218)

Utilizator danny794Dan Danaila danny794 Data 11 noiembrie 2015 13:30:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>

#define NMAX 2000005

using namespace std;

char A[NMAX], B[NMAX];
int pos[NMAX], N, res[1005];

void computePos() {
  int index = 0;
  pos[index] = -1;
  while (A[++index] != '\0') {
    int aux = pos[index - 1];
    while (aux != -1 && A[index] != A[aux + 1]) {
      aux = pos[aux];
    }
    if (A[index] == A[aux + 1]) {
      pos[index] = aux + 1;
    } else {
      pos[index] = -1;
    }
  }
}

void readInput() {
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  scanf("%s\n", A);
  scanf("%s", B);
}

void match() {
  int bIndex = 0;
  int aIndex = 0;
  while (B[bIndex] != '\0' && N < 1000) {
    while (A[aIndex] != '\0' && B[bIndex] != '\0' && A[aIndex] == B[bIndex]) {
      aIndex++;
      bIndex++;
    }
    if (aIndex == 0) {
      bIndex++;
      continue;
    }
    if (A[aIndex] == '\0') {
      N++;
      res[N] = bIndex - aIndex;
    }
    aIndex = pos[aIndex - 1] + 1;
  }
}

void printSol() {
  printf("%d\n", N);
  for (int i = 1; i <= N; i++) {
    printf("%d ", res[i]);
  }
}

int main() {
  readInput();
  computePos();
  match();
  printSol();
  return 0;
}