Cod sursa(job #2902413)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 16 mai 2022 11:59:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>

#define MAX_LEN 2000000

using namespace std;

FILE *fin, *fout;

char v[MAX_LEN * 2 + 1];
int vSize;
int ans[MAX_LEN];
int ansSize;
int longestPrefix[MAX_LEN * 2 + 1];
int lef, righ;
int size1, size2;

int readWord() {
  int wordSize;
  char ch;

  wordSize = 0;
  ch = fgetc(fin);
  while ( ch != '\n' && ch != EOF ) {
    v[vSize] = ch;
    vSize++;
    wordSize++;
    ch = fgetc(fin);
  }

  return wordSize;
}

int calcLen(int pos) {
  int i, ans;

  if ( righ <= pos ) {
    lef = righ = pos;
    while ( righ < vSize && v[righ] == v[righ - lef] ) {
      righ++;
      i++;
    }
    righ--;

    ans = righ - lef + 1;
  } else {
    if ( longestPrefix[pos - lef] < righ - pos + 1 ) {
      ans = longestPrefix[pos - lef];
    } else {
      lef = pos;
      while ( righ < vSize && v[righ] == v[righ - lef] )
        righ++;
      righ--;
      ans = righ - pos + 1;
    }
  }

  return ans;
}

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

  int i;

  vSize = 0;
  size1 = readWord();
  v[vSize] = '*';
  vSize++;
  size2 = readWord();

  ansSize = 0;
  if ( size1 <= size2 ) {
    lef = righ = 0;
    for ( i = 1; i < vSize; i++ ) {
      longestPrefix[i] = calcLen(i);
      if ( longestPrefix[i] == size1 && i > size1 ) {
        if ( ansSize <= 1000 )
          ans[ansSize] = i - size1 - 1;
        ansSize++;
      }
    }
  }

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

  fclose(fin);
  fclose(fout);

  return 0;
}