Cod sursa(job #2340364)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 10 februarie 2019 12:50:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in ("strmatch.in");
ofstream out("strmatch.out");
const int NR = 2000005 ;
char s [ NR ] , t [ NR ] ;
int p [ NR ] , l , nrap , sol [ 1002 ] , i , n , m ;
int main()
{
 in >> s + 1 ;
 in >> t + 1 ;
 n = strlen( s + 1 ) ;
 m = strlen( t + 1 ) ;
 p [ 1 ] = 0 ;
 for ( i = 2 ; i <= n ; ++ i )
 {
    while ( l && s [ i ] != s [ l + 1 ] )   l = p [ l ] ;
    if ( s [ i ] == s [ l + 1 ] )   l ++ ;
    p [ i ] = l ;

 }
 l = 0 ;
 for ( i = 1 ; i <= m ; ++ i )
 {
     while ( l && t [ i ] != s [ l + 1 ] )  l = p [ l ] ;
     if ( t [ i ] == s [ l + 1 ] )  l ++ ;
     if ( l == n )
     {
         nrap ++ ;
         if ( nrap <= 1000 )
         {
             sol [ nrap ] = i - n ;
         }
         l = p [ l ] ;
     }

 }
 out << nrap << '\n' ;
 nrap = min ( nrap , 1000 ) ;
 for ( i = 1 ; i <= nrap ; ++ i )   out << sol [ i ] << ' ' ;
    return 0;
}