Cod sursa(job #2847279)

Utilizator euyoTukanul euyo Data 10 februarie 2022 16:08:54
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

const int MAXN = 1000005; 

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

void KMP( const string &s, int lps[] ) {
  int q = -1, n = s.length();

  for ( int i = 1; i < n; ++i ) {
    while ( q > 0 && s[q+1] != s[i] ) {
      q = lps[q];
	}
	if ( s[q+1] == s[i] ) {
	  ++q;
	}
    lps[i] = q+1;
  }
}

int lps[MAXN];
vector<int> sol;

int main() {
  string s, patt;
  int q = -1;
  
  fin >> patt >> s;
  KMP(patt, lps);
  
  for ( int i = 0; i < s.length(); ++i ) {
	while ( q > 0 && patt[q+1] != s[i] ) {
	  q = lps[q];
	}
	if ( patt[q+1] == s[i] ) {
	  ++q;
	}	
	if ( q+1 == patt.length() ) {
	  if ( sol.size() < 1000 ) sol.push_back( i - patt.length() + 1 );
	}
  }
  fout << sol.size() << "\n";
  for ( int i = 0; i < sol.size(); ++i ) {
	fout << sol[i] << " ";
  }
  fin.close();
  fout.close();
  return 0;
}