Cod sursa(job #1551845)

Utilizator tudorcomanTudor Coman tudorcoman Data 16 decembrie 2015 19:10:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <cstring>
#include <vector>

const int len = 2e6;
char A[1 + len + 1];
char B[1 + len + 1];

int pi[1 + len], nA, nB;
std :: vector<int> sol;

int main() {
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);

  gets(A + 1);
  gets(B + 1);

  nA = strlen(A + 1);
  nB = strlen(B + 1);

  pi[1] = 0;
  int x = pi[1];
  for(int i = 2; i <= nA; ++ i) {
    while(x > 0 and A[i] != A[x + 1])
      x = pi[x];
    if(A[i] == A[x + 1])
      ++ x;
    pi[i] = x;
  }

  x = 0;
  for(int i = 1; i <= nB; ++ i) {
    while(x > 0 and B[i] != A[x + 1])
      x = pi[x];
    if(B[i] == A[x + 1])
      ++ x;
    if(x == nA) {
      sol.push_back(i - nA);
      x = pi[x];
    }
  }

  printf("%u\n", sol.size());
  int lim = sol.size();
  if(1000 < lim)
    lim = 1000;
  for(int i = 0; i < lim; ++ i)
    printf("%d ", sol[i]);
  printf("\n");
  return 0;
}