Cod sursa(job #2902046)

Utilizator Teodor94Teodor Plop Teodor94 Data 15 mai 2022 09:56:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define INVALID_CHAR '$'

#define MAX_STR 2000000
#define MAX_PATTERN 2000000

#define MAX_MATCHES 1000

char str[MAX_STR + MAX_PATTERN + 1];
int patternSize, strSize;

int z[MAX_STR + MAX_PATTERN + 1];

int matches[MAX_MATCHES], noMatches;

void computeZ() {
  int i, left, right;

  left = right = 0;
  for (i = 1; i < strSize; ++i) {
    if (i > right) {
      left = right = i;
      while (right < strSize && str[right - left] == str[right])
        ++right;
      --right;

      z[i] = right - left + 1;
    } else if (z[i - left] < right - i + 1) {
      z[i] = z[i - left];
    } else {
      left = i;
      while (right < strSize && str[right - left] == str[right])
        ++right;
      --right;

      z[i] = right - left + 1;
    }
  }
}

int main() {
  FILE *fin, *fout;
  fin = fopen("strmatch.in", "r");
  fout = fopen("strmatch.out", "w");

  int i;

  fscanf(fin, "%s\n", str);
  patternSize = strlen(str);

  str[patternSize] = INVALID_CHAR;

  fscanf(fin, "%s", str + patternSize + 1);
  strSize = strlen(str);

  computeZ();

  for (i = 0; i < strSize; ++i)
    if (z[i] == patternSize) {
      if (noMatches < MAX_MATCHES)
        matches[noMatches] = i - patternSize - 1;
      ++noMatches;
    }

  fprintf(fout, "%d\n", noMatches);
  noMatches = min(noMatches, MAX_MATCHES);
  for (i = 0; i < noMatches; ++i)
    fprintf(fout, "%d ", matches[i]);

  fclose(fin);
  fclose(fout);
  return 0;
}