Cod sursa(job #1647400)

Utilizator gerd13David Gergely gerd13 Data 10 martie 2016 20:24:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstring>
#include <cstdio>
#include <fstream>
#include <queue>

using namespace std ;

const int NMAX = 20000005 ;

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


inline void PREFIX()
{
    int K = 0 ;
    prefix[1] = 0 ;
    for(int i = 2 ; i < strlen(A) ; ++ 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 < strlen(B) ; ++ i)
    {
        while(Q && B[i] != A[Q + 1])
            Q = prefix[Q] ;

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

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

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

}

ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;

int main()
{


    fin.getline(A, NMAX) ;
    fin.getline(B, NMAX) ;



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

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

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

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

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

}