Cod sursa(job #1394843)

Utilizator Burbon13Burbon13 Burbon13 Data 20 martie 2015 18:59:27
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define mx 2000069

char A[mx] , B[mx] , pi[mx] , pos[1069] ;
int a , b ;

void prefix()
{
    int q = 0 ;
    pi[1] = 0 ;

    for ( int i = 2 ; i <= a ; i ++ )
    {
        while ( q && A[q+1] != A[i] )
            q = pi[q] ;
        if ( A[q+1] == A[i] )
            q ++ ;
        pi[i] = q ;
    }
}

int main()
{
    freopen( "strmatch.in" , "r" , stdin ) ;
    freopen( "strmatch.out" , "w" , stdout ) ;

    scanf( "%s" , A + 1 ) ;
    a = strlen(A+1) ;
    scanf( "%s" , B + 1 ) ;
    b = strlen(B+1) ;

    prefix() ;

    int q = 0 , n = 0 ;

    for ( int i = 1 ; i <= b; i ++ )
    {
        while ( q && A[q+1] != B[i] )
            q = pi[q] ;
        if ( A[q+1] == B[i] )
            q ++ ;
        if ( q == a )
        {
            q = pi[a] ;
            n ++ ;
            if ( n <= 1000 )
                pos[n] = i - a ;
        }
    }

    printf( "%d\n" , n ) ;

    for ( int i = 1 ; i <= min(n,1000) ; i ++ )
        printf( "%d " , pos[i] ) ;

    return 0;
}