Cod sursa(job #889236)

Utilizator PatrikStepan Patrik Patrik Data 24 februarie 2013 12:55:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
    #include<cstdio>
    #include<cstring>
    #include<fstream>
    #define MAX 2000002
    using namespace std;
    char N[MAX] ,M[MAX] ;
    int pi[MAX] , k , n , m  , nr , poz[1001];

    void citire();
    void prefix();
    void kmp();
    void tipar();

    int main()
    {
        citire();
        prefix();
        kmp();
        tipar();
        return 0;
    }

    void citire()
    {
        freopen("strmatch.in" , "r" , stdin );
        scanf("%s\n%s" , N+1 , M+1 );
        n = m = 1;
        for(;N[n]; ++n);n--;
        for(;M[m]; ++m);m--;
    }

    void prefix()
    {
        k = 0;
        for( int i = 2 ; i <= n ; ++i )
        {
            while(k && N[k+1] != N[i])
                k = pi[k];
            if(N[i] == N[k+1])
                k++;
            pi[i] = k;
        }
    }

    void kmp()
    {
        k = 0;
        for( int i = 1 ; i <= m ; ++i )
        {
            while(k && N[k+1] != M[i])
                k = pi[k];
            if(M[i] == N[k+1])
                k++;
            if(k == n )
            {
                nr++;
                if(nr<=1000)
                    poz[nr] = i-n;
            }
        }
    }

    void tipar()
    {
          freopen("strmatch.out" , "w" , stdout );
          printf("%d\n" , nr );
          for( int i = 1 ; i <= min(nr,1000) ; ++i )
            printf("%d ",poz[i]);
    }