Cod sursa(job #1551848)

Utilizator spatarelDan-Constantin Spatarel spatarel Data 16 decembrie 2015 19:20:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <cstring>
#include <vector>

using std :: vector;

const int len = 2e6;

char A[1 + len + 1];
char B[1 + len + 1];

int pi[1 + len];
vector<int> sol;

void compute(char *A, int* pi) {
  int nA = strlen(A + 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;
  }
}

void find(char *A, char *B, int *pi, vector<int> &sol) {
  int x = 0;
  int nA = strlen(A + 1);
  int nB = strlen(B + 1);
  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];
    }
  }
}

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

  scanf("%s", A + 1);
  scanf("%s", B + 1);

  compute(A, pi);
  find(A, B, pi, sol);

  printf("%d\n", (int)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;
}