Cod sursa(job #864979)

Utilizator drobertDumitru Robert drobert Data 25 ianuarie 2013 21:41:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std ;
vector < long > sol ;
char a [ 2000007 ] , b [ 2000007 ] ;
long n , m , x ;
long p [ 2000007 ] ;
void fa_x ( char b [ ] ,long i )
{
    while ( x > 0 && a [ x + 1 ] != b [ i ] )
        x = p [ x ] ;
    if ( a [ x + 1 ] == b [ i ] )
            ++ x ;
}
void make_prefix ( )
{
    for ( long i = 2 ; i <= m ; ++ i )
    {
        fa_x ( a , i ) ;
        p [ i ] = x ;
    }
}
int main()
{
    long nr2 = 0  ;
    freopen ( "strmatch.in" , "r" , stdin ) ;
    freopen ( "strmatch.out" , "w" , stdout ) ;
    a [ 0 ] = ' ' ;
    gets ( a + 1 ) ;
    b [ 0 ] = ' ' ;
    gets ( b + 1 ) ;
    m = strlen ( a ) - 1 ;
    n = strlen ( b ) - 1 ;
    make_prefix ( ) ;
    x = 0 ;
    long ok = 0 ;
    for( long i = 1 ; i <= n && ok == 0  ; ++ i )
    {
        fa_x ( b , i ) ;
        if ( x == m )
        {
            x = p [ m ] ;
            sol . push_back ( i - m ) ;
        }
    }
    long nr = 1000 ;
    printf ( "%ld\n" , ( long ) sol . size ( ) ) ;
    for( long i = 0 ; i < min ( nr , ( long ) sol . size ( ) ) ; ++ i )
        printf ( "%ld ", sol [ i ] ) ;
    return 0 ;
}