Cod sursa(job #2834675)

Utilizator andreic06Andrei Calota andreic06 Data 17 ianuarie 2022 14:47:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;
const int LEN_MAX = 2e6;
const char BORD = '$';
const int LIMIT = 1e3;
const int STOP = 0;

int lps[1 + LEN_MAX];
void process_lps ( string text ) {
    int n = text.size ();
    lps[0] = STOP;
    for ( int i = 1; i < n; i ++ ) {
       int prev = lps[i - 1];
       while ( prev != STOP && text[i] != text[prev] )
          prev = lps[prev - 1];
       ///cout << prev << " ";
       if ( text[i] == text[prev] )
         lps[i] = prev + 1;
       else
         lps[i] = 0;
    }
}
/// ABA$CABBCABABAB

ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
int main()
{
   string pattern, text;
   fin >> pattern >> text;
   int target = pattern.size ();
   pattern += BORD; pattern += text;
   int total = pattern.size ();
   process_lps ( pattern );

   vector<int> ans;
   for ( int i = target; i < total && (int) ans.size () < LIMIT; i ++ )
      if ( lps[i] == target )
        ans.push_back ( i );

   fout << ans.size () << "\n";
   for ( auto pos : ans )
      fout << pos - 2 * target << " ";
    return 0;
}