Cod sursa(job #2905713)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 23 mai 2022 10:52:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>

#define MAX_LEN 2000000
#define MAXANS 1000

using namespace std;

char str[MAX_LEN];
int strSize;
char pattern[MAX_LEN];
int patternSize;
int longestPrefixSufix[MAX_LEN];
int ans[MAXANS];
int ansSize;

FILE *fin, *fout;

void precalcLongestPrefixSufix() {
  int i, i2;

  longestPrefixSufix[0] = 0;
  for ( i = 1; i < patternSize; i++ ) {
    i2 = longestPrefixSufix[i - 1];
    while ( i2 && pattern[i] != pattern[i2]) {
      i2 = longestPrefixSufix[i2];
    }
    longestPrefixSufix[i] = i2 + (pattern[i] == pattern[i2]);
  }
}

void readLine(char* v, int& sizeV) {
  char ch;

  sizeV = 0;
  ch = fgetc(fin);
  while ( ch != '\n' && ch != EOF ) {
    *(v + sizeV) = ch;
    sizeV++;
    ch = fgetc(fin);
  }
}

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

  readLine(pattern, patternSize);
  readLine(str, strSize);
  precalcLongestPrefixSufix();

  int i, i2;

  i = i2 = 0;
  while ( i < strSize ) {
    if ( str[i] == pattern[i2] ) {
      i2++;
      i++;
      if ( i2 == patternSize ) {
        if ( ansSize < 1000 )
          ans[ansSize] = i - patternSize;
        ansSize++;
      }
    } else {
      if ( i2 > 0 )
        i2 = longestPrefixSufix[i2 - 1];
      else
        i++;
    }
  }

  fprintf(fout, "%d\n", ansSize);
  for ( i = 0; i < min(ansSize, 1000); i++ ) {
    fprintf(fout, "%d ", ans[i]);
  }
  fprintf(fout, "\n");

  fclose(fin);
  fclose(fout);

  return 0;
}