Cod sursa(job #1631968)

Utilizator xtreme77Patrick Sava xtreme77 Data 5 martie 2016 20:27:57
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "strmatch.in" ;
const char OUT [ ] = "strmatch.out" ;

using namespace std ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

const int MAX = 4e6 + 14 ;

char sir [ MAX ] ;

int z [ MAX ] ;

int cate ;
vector < int > sol ;

int main ( void )
{
    cin >> ( sir + 1 ) ;
    int l = strlen ( sir + 1 ) ;
    sir [ l + 1 ] = '#' ;
    cin >> ( sir + l + 2 ) ;
    int n = strlen ( sir + 1 ) ;
    int L = 1 ;
    int R = 1 ;
    z [ 1 ] = 0 ;
    int bucluc = l + 1 ;
    FORN ( i , 2 , n )
    {
        if ( sir [ i ] == '#' ) continue ;
        if ( R < i ) {
            while ( i + z [ i ] <= n and sir [ i + z [ i ] ] == sir [ z [ i ] + 1 ] )
                ++ z [ i ] ;
            R = i + z [ i ] - 1 ;
            L = i ;
            if ( z [ i ] == l and i > l ) {
                ++ cate ;
                if ( cate <= 1000 ) {
                    sol.pb ( i - ( l + 1 ) - 1 ) ;
                }
            }
            //cout << z [ i ] << ' ' ;
            continue ;
        }
        int oo = i - L + 1 ;
        z [ i ] = z [ oo ] ;
        if ( i < R ) {
            z [ i ] = min ( z [ oo ] , R - i ) ;
        }
        while ( i + z [ i ] <= n and sir [ i + z [ i ] ] == sir [ z [ i ] + 1 ] )
            ++ z [ i ] ;
        if ( i + z [ i ] - 1 > R ) {
            L = i ;
            R = i + z [ i ] - 1 ;
        }
        if ( z [ i ] == l and i > l ) {
            ++ cate ;
            if ( cate <= 1000 ) {
                sol.pb ( i - ( l + 1 ) - 1 ) ;
            }
        }
        //cout << z [ i ] << ' ' ;
    }
    //return 0 ;
    //cout << endl ;
    cout << cate << '\n' ;
    for ( auto x : sol )
        cout << x << ' ' ;
    return 0;
}