Cod sursa(job #2808012)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 24 noiembrie 2021 14:17:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int LMAX = 2000000;

int la, lb;
char a[LMAX + 5], b[LMAX + 5];
int za[LMAX + 5], zb[LMAX + 5];
vector<int> matches;

void calc_za() {
  za[0] = 0;

  for(int i = 1, l = 0, r = 0; i < la; i++) {
    if(i <= r) /// ma aflu in interiorul prefixului deja calculat, [l, r]
      za[i] = min(za[i - l], r - i + 1);

    /// adaug cat de multe caractere pot la prefixul curent
    while(i + za[i] < la && a[i + za[i]] == a[za[i]])
      za[i]++;

    /// actualizez [l, r] astfel incat r sa fie maxim
    if(i + za[i] - 1 > r)
      l = i, r = i + za[i] - 1;
  }
}

void calc_zb() {
  for(int i = 0, l = 0, r = -1; i < lb; i++) {
    if(i <= r)
      zb[i] = min(za[i - l], r - i + 1);

    while(i + zb[i] < lb && zb[i] < la && a[zb[i]] == b[i + zb[i]])
      zb[i]++;

    if(i + zb[i] - 1 > r)
      l = i, r = i + zb[i] - 1;

    if(zb[i] == la)
      matches.push_back(i);
  }
}

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

  scanf("%s %s", a, b);
  la = strlen(a);
  lb = strlen(b);

  calc_za();
  calc_zb();

  printf("%d\n", matches.size());
  for(int x: matches)
    printf("%d ", x);

  return 0;
}