Cod sursa(job #1789772)

Utilizator deividFlorentin Dumitru deivid Data 27 octombrie 2016 15:21:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <cstring>
#include <vector>

#define maxdim 2000005

using namespace std;

int n, m;
int pi[maxdim];
char A[maxdim], B[maxdim];
vector<int> sol;

inline void prefix() {
  
  int k = 0;
  for (int i = 2; i <= n; ++i) {
    while (k > 0 && A[k + 1] != A[i]) {
      k = pi[k];
    }
    if (A[k + 1] == A[i]) {
      ++k;
    }
    pi[i] = k;
  }
}

int main() {
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  
  scanf("%s\n%s", A + 1, B + 1);
  n = strlen(A + 1);
  m = strlen(B + 1);

  prefix();

  int matches = 0;
  int k = 0;
  for (int i = 1; i <= m; ++i) {
    while (k > 0 && B[i] != A[k + 1]) {
      k = pi[k];
    }
    if (B[i] == A[k + 1]) {
      ++k;
    }
    if (k == n) {
      ++matches;
      if (matches < 1000) {
        sol.push_back(i - n);
      }
    }
  }

  printf("%d\n", matches);
  for (int match : sol) {
    printf("%d ", match);
  }
  printf("\n");

  return 0;
}