Cod sursa(job #2905476)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 22 mai 2022 00:48:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
// Mihai Priboi

#include <bits/stdc++.h>

using namespace std;

#define MAXN 4000000

int z[MAXN];
char s[MAXN];
int sSize, pSize;
int rez;

void computeZ() {
  int l, r, i;

  l = r = 0;
  for( i = 0; i < sSize && rez < 1000; i++ ) {
    if( i > r ) {
      l = r = i;
      while( r < sSize && s[r - i] == s[r] ) r++;
      r--;
      z[i] = r - l + 1;
    }
    else {
      if( z[i - l] < r - i + 1 )
        z[i] = z[i - l];
      else {
        l = i;
        while( r < sSize && s[r - i] == s[r] ) r++;
        r--;
        z[i] = r - l + 1;
      }
    }
    if( z[i] == pSize ) rez++;
  }
}

int main() {
  FILE *fin, *fout;
  int i;

  fin = fopen( "strmatch.in", "r" );

  fscanf( fin, "%s\n", s );
  pSize = strlen(s);
  fscanf( fin, "%s", s + pSize + 1 );

  fclose( fin );

  s[pSize] = '$';
  sSize = strlen(s);

  computeZ();

  fout = fopen( "strmatch.out", "w" );

  fprintf( fout, "%d\n", rez );
  for( i = pSize + 1; i < sSize && rez > 0; i++ ) {
    if( z[i] == pSize ) {
      fprintf( fout, "%d ", i - pSize - 1 );
      rez--;
    }
  }

  fclose( fout );
  return 0;
}