Cod sursa(job #2808031)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 24 noiembrie 2021 14:45:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 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 z[LMAX + 5];

int nr_matches;
int matches[LMAX + 5];

void calc_z() {
  z[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]
      z[i] = min(z[i - l], r - i + 1);

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

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

void calc_matches() {
  for(int i = 0, l = 0, r = 0; i < lb; i++) {
    int crt = 0;

    if(i <= r)
      crt = min(z[i - l], r - i + 1);

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

    if(i + crt - 1 > r)
      l = i, r = i + crt - 1;

    if(crt == la)
      matches[++nr_matches] = 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_z();
  calc_matches();

  printf("%d\n", nr_matches);
  for(int i = 1; i <= nr_matches; i++)
    printf("%d ", matches[i]);

  return 0;
}