Cod sursa(job #2901992)

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

#define MAX_STR 2000000
#define MAX_PATTERN 2000000

#define MAX_MATCHES 1000

char str[MAX_STR];
int strSize;

char pattern[MAX_PATTERN];
int patternSize;

int prefix[MAX_PATTERN];

int matches[MAX_MATCHES];

void computePrefix() {
  int i, prefixLen;

  prefix[0] = 0;
  for (i = 1; i < patternSize; ++i) {
    prefixLen = prefix[i - 1];
    while (prefixLen && pattern[i] != pattern[prefixLen])
      prefixLen = prefix[prefixLen - 1];

    if (pattern[i] == pattern[prefixLen])
      prefix[i] = prefixLen + 1;
  }
}

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

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

  computePrefix();

  int i, j, noMatches;

  noMatches = 0;
  i = j = 0;
  while (i < strSize)
    if (str[i] == pattern[j]) {
      ++i, ++j;

      if (j == patternSize) {
        if (noMatches < MAX_MATCHES)
          matches[noMatches] = i - j;
        ++noMatches;

        j = prefix[j - 1];
      }
    } else {
      if (j > 0)
        j = prefix[j - 1];
      else
        ++i;
    }

  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;
}