Cod sursa(job #2742888)

Utilizator euyoTukanul euyo Data 22 aprilie 2021 10:47:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );

const int MAXL = 2000002;
const int MAX_OUT = 1000;

char t[MAXL], w[MAXL];
int n, m;
int pi[MAXL];

vector<int> sol;

void precalc() {
  int q = 0;
  for ( int i = 2; i <= m; ++i ) {
    while ( q > 0 && w[q] != w[i - 1] ) {
      q = pi[q];
	}
	if ( w[q] == w[i - 1] ) {
	  ++q;
	}
    pi[i] = q;
  }
}

int main() {
  int q = 0, cnt = 0;

  fin >> w >> t;
  n = strlen( t );
  m = strlen( w );
  precalc();
  
  for ( int i = 1; i <= n; ++i ) {
	while ( q > 0 && w[q] != t[i - 1] ) {
	  q = pi[q];
	}
	if ( w[q] == t[i - 1] ) {
	  ++q;
	}	
	if ( q == m ) {
	  if ( sol.size() < MAX_OUT ) {
		sol.push_back( i );
	  }
	  ++cnt;
	}
  }
  fout << cnt << "\n";
  for ( int i = 0; i < (int)sol.size(); ++i ) {
	fout << sol[i] - m << " ";
  }
  fin.close();
  fout.close();
  return 0;
}