Cod sursa(job #2902428)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 16 mai 2022 12:15:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 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 l, r;
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 ( r <= pos ) {
    l = r = pos;
    while ( r < vSize && v[r] == v[r - l] ) {
      r++;
      i++;
    }
    r--;

    ans = r - l + 1;
  } else {
    if ( longestPrefix[pos - l] < r - pos + 1 ) {
      ans = longestPrefix[pos - l];
    } else {
      l = pos;
      while ( r < vSize && v[r] == v[r - l] )
        r++;
      r--;
      ans = r - 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 ) {
    l = r = 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 < min(1000, ansSize); i++ ) {
    fprintf(fout, "%d ", ans[i]);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}