Cod sursa(job #1647374)

Utilizator gerd13David Gergely gerd13 Data 10 martie 2016 20:19:46
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstring>
#include <cstdio>
#include <iostream>
#include <queue>

using namespace std ;

const int NMAX = 20000005 ;

int prefix[NMAX], sol, S[NMAX];
string A, B ;


inline void PREFIX()
{
    int K = 0 ;
    prefix[1] = 0 ;
    for(int i = 2 ; i < A.size(); ++ i)
    {
        while(K > 0 && A[i] != A[K + 1])
            K = prefix[K] ;

        if(A[i] == A[K + 1])
            K ++ ;
        prefix[i] = K ;
    }
}


inline void KMP()
{
    int Q = 0 ;
    for(int i = 1 ; i < B.size() ; ++ i)
    {
        while(Q && B[i] != A[Q + 1])
            Q = prefix[Q] ;

        if(A[Q + 1] == B[i])
            Q ++  ;

        if(Q == A.size() -1)
        {
            Q = prefix[Q] ;

            sol ++ ;
            if(sol <= 1000)
            {
                S[sol] = i - A.size() + 1 ;
            }
        }
    }

}

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


    cin >> A >> B ;

    A.push_back(' ') ;
    B.push_back(' ') ;

    for(int i = A.size() - 1 ; i >= 0 ; -- i)
        A[i + 1] = A[i] ;

    for(int i = B.size() - 1 ; i >= 0 ; -- i)
        B[i + 1] = B[i] ;

    A[0] = ' ' ;
    B[0] = ' ' ;

    PREFIX() ;
    KMP() ;
    cout << sol << '\n' ;

    for(int i = 1 ; i <= min(sol, 1000) ; ++i)
        cout << S[i] << ' ' ;

}