Cod sursa(job #3297554)

Utilizator Arhiva_Educationala_2Arhiva Educationala doi Arhiva_Educationala_2 Data 22 mai 2025 20:35:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> kmp( const std::string &str ) {
  std::vector<int> lcp(str.size(), 0);
  for( int i = 1; i < (int)str.size(); i++ ){
    int tactu = lcp[i - 1];

    while( tactu && str[tactu] != str[i] )
      tactu = lcp[tactu - 1];

    if( str[tactu] == str[i] )
      lcp[i] = 1 + tactu;
    else
      lcp[i] = 0;
  }

  return lcp;
}

int main() {
  std::ifstream fin( "strmatch.in" );
  std::ofstream fout( "strmatch.out" );

  std::string text;
  std::string pat;

  fin >> pat >> text;
  std::string totul = pat + '|' + text;
  std::vector<int> mata = kmp( totul );

  std::vector<int> out;
  for( int i = 0; i < (int)text.size(); i++ )
    if( mata[(int)pat.size() + 1 + i] >= (int)pat.size() )
      out.push_back( i + 1 - (int)pat.size() );

  fout << out.size() << '\n';
  if( out.size() > 1000 )
    out.resize( 1000 );
  for( int x : out ) fout << x << ' '; fout << '\n';

  return 0;
}