Cod sursa(job #1694624)

Utilizator xtreme77Patrick Sava xtreme77 Data 25 aprilie 2016 18:05:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include <bits/stdc++.h>

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 fin ( IN ) ;
ofstream fout ( OUT ) ;

const int MAX = 2e6 + 14 ;
const unsigned int baza = 71 ;

char A [ MAX ] ;
char B [ MAX ] ;
unsigned int h [ MAX ] ;
unsigned int p [ MAX ] ;

unsigned int hash_pe_interval ( int i , int j )
{
    return h [ i ] - h [ j + 1 ] * p [ j - i + 1 ] ;
}

vector < int > pozitii ;

int main()
{
    fin >> ( A + 1 ) ;
    fin >> ( B + 1 ) ;
    int lenA = strlen ( A + 1 ) ;
    int lenB = strlen ( B + 1 ) ;
    p [ 0 ] = 1 ;
    FORN ( i , 1 , lenB ) {
        p [ i ] = p [ i - 1 ] * baza ;
    }
    FORNBACK ( i , lenB , 1 ) {
        h [ i ] = h [ i + 1 ] * baza + B [ i ] ;
    }
    unsigned hashA = 0 ;
    FORNBACK ( i , lenA , 1 ) {
        hashA = hashA * baza + A [ i ] ;
    }
    int limita = lenB - lenA + 1 ;
    int aparitii = 0 ;
    FORN ( i , 1 , limita ) {
        if ( hash_pe_interval( i , i + lenA - 1 ) == hashA ) {
            ++ aparitii ;
            if ( aparitii <= 1000 ) {
                pozitii.pb ( i - 1 ) ;
            }
        }
    }
    fout << aparitii << '\n' ;
    for ( auto x : pozitii ) {
        fout << x << ' ' ;
    }
    return 0;
}