Cod sursa(job #2905480)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 22 mai 2022 01:15:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
// Mihai Priboi

#include <bits/stdc++.h>

using namespace std;

#define MAXN 2000000

int prefix[MAXN];
char s[MAXN + 1], pattern[MAXN + 1];
int pSize, sSize;

void computePrefixes() {
  int i, pLen;

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

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

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

  fin = fopen( "strmatch.in", "r" );
  fscanf( fin, "%s\n%s", pattern, s );
  fclose( fin );

  pSize = strlen(pattern);
  sSize = strlen(s);

  computePrefixes();

  vector<int> rez;

  i = j = 0;
  while( i < sSize ) {
    if( s[i] == pattern[j] ) {
      i++;
      j++;

      if( j == pSize ) {
        rez.push_back(i - j);
        j = prefix[j - 1];
      }
    }
    else {
      if( j > 0 )
        j = prefix[j - 1];
      else
        i++;
    }
  }
  
  fout = fopen( "strmatch.out", "w" );

  fprintf( fout, "%d\n", rez.size() );
  for( i = 0; i < rez.size() && i < 1000; i++ )
    fprintf( fout, "%d ", rez[i] );

  fclose( fout );
  return 0;
}