Cod sursa(job #964565)

Utilizator matei_cChristescu Matei matei_c Data 21 iunie 2013 15:03:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std ;

#define maxn 10001

char S[maxn], W[maxn] ;
int T[maxn] ;
int lenS, lenW ;

vector<int> sol ;

void prefix()
{
    T[0] = -1 ;
    T[1] = 0 ;
    int k = 0 ;
    int poz = 2 ;

    while( poz < lenW )
    {
        if( W[k] == W[ poz - 1 ] )
        {
            ++k ;
            T[poz] = k ;
            ++poz ;
        }
        else
        {
            if( k > 0 )
                k = T[k] ;
            else
            {
                T[poz] = 0 ;
                ++poz ;
            }
        }
    }
}

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

    scanf("%s\n", W);
    scanf("%s", S);

    lenS = strlen(S) ;
    lenW = strlen(W) ;

    prefix() ;

    int poz = 0 ;
    int start = 0 ;

    while( poz + start < lenS )
    {
        if( W[poz] == S[ start + poz ] )
        {
            if( poz ==  lenW - 1 )
            {
                sol.push_back(start) ;

                start = start + poz - T[poz] ;

                if( T[poz] > -1 )
                    poz = T[poz] ;
                else
                    poz = 0 ;
                continue;
            }

            ++poz ;
        }
        else
        {
            start = start + poz - T[poz] ;

            if( T[poz] > -1 )
                poz = T[poz] ;
            else
                poz = 0 ;
        }
    }

    printf("%d\n", sol.size() );

    for(size_t i = 0; i < sol.size(); ++i )
        printf("%d ", sol[i]);

    return 0 ;
}