Cod sursa(job #1632357)

Utilizator gerd13David Gergely gerd13 Data 6 martie 2016 02:11:47
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <cstring>

using namespace std;

const int NMAX = 2000005 ;

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

char A[NMAX], B[NMAX] ;
int N, M, pi[NMAX], K, sol, SOL[NMAX];

inline void Prefix()
{
    N = strlen(A) - 1 ;
    K = 0 ;

    for(int i = 2 ; i <= N ; ++ i)
    {
        while(K > 0 && A[K + 1] != A[i])
            K = pi[K] ;
        if(A[K + 1] == A[i])
            K = K  + 1 ;
        pi[i] = K ;
    }
}

inline void MATCH()
{
    M = strlen(B) - 1 ;
    N = strlen(A) - 1;
    K = 0 ;
    for(int i = 1 ; i <= M ; ++ i)
    {
        while(K > 0 && A[K + 1] != B[i])
            K = pi[K] ;
        if(A[K + 1] == B[i])
            K = K + 1 ;

        if(K == N)
        {
            sol ++ ;
            if(sol < 1001)
                SOL[sol] = i - N   ;
            K = 0 ;
        }
    }


}

int main()
{
    fin >> A >> B ;

    Prefix() ;
    MATCH() ;

    fout << sol << '\n' ;

    for(int i = 1 ; i <= sol ; ++ i)
        fout << SOL[i] << ' ' ;

    fin.close() ;
    fout.close() ;
    return 0;
}