Cod sursa(job #2637202)

Utilizator andreic06Andrei Calota andreic06 Data 21 iulie 2020 20:18:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>

using namespace std;
const int N = 2e6;
const int M = 2e6;
char txt[N], pat[M];
int lps[M]; /// lenght prefix&sufix
int result[N];
int n, m;

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

void process_lps () {

    lps[0] = 0; /// lps[0] e mereu 0

    int i = 1, len = 0;
    while ( i < m ) {
       if ( pat[i] == pat[len] ) {
         len ++ ;
         lps[i] = len;
         i ++;
       }
       else if ( len != 0 )
         len = lps[len-1];
       else
         len = 0, i ++;
    }
}

int main()
{
   char ch;
   m = 0;
   ch = fin.get ();
   while ( ch != '\n' ){
      pat[m++] = ch;
      ch = fin.get ();
   }

   n = 0, ch = fin.get ();
   while ( ch != EOF && ch != '\n' ){
      txt[n++] = ch;
      ch = fin.get ();
   }

   process_lps ();

   int i = 0, j = 0;
   int n_res = 0;
   while ( i < n ) {
      if ( pat[j] == txt[i] )
        i ++, j ++;
      if ( j == m ) {
        result[n_res++] = i - j;
        j = lps[j-1];
      }
      else if ( i < n && pat[j] != txt[i] ){
        if ( j > 0 )
          j = lps[j-1];
        else
          i ++;
      }
   }

   fout << n_res << '\n';
   for ( int i = 0; i < min ( n_res, 1000 ); i ++ )
      fout << result[i] << ' ';

    return 0;
}