Cod sursa(job #1998376)

Utilizator andreismara97Smarandoiu Andrei andreismara97 Data 7 iulie 2017 16:52:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<cstring>
using namespace std;

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

#define Nmax 2000001

char A[Nmax], B[Nmax];
int pi[Nmax], pos[Nmax], n = 0;

void getPrefix()
{
    int i = 0;
    pi[0] = 0;
    for( int j = 1; j<strlen(A); j++ )
    {
        while( i && A[i] != A[j] )
            i = pi[i-1];
        if( A[i] == A[j] )
            i++;
        pi[j] = i;
    }

//    for( int j = 0; j < strlen(A); j++ )
//        out<<pi[j]<<'\n';
}

int main()
{

    in.getline(A, Nmax);
    in.getline(B, Nmax);

    getPrefix();

    int i = 0;
    for( int j = 0; j < strlen(B); j++ )
    {
        while( i && A[i] != B[j])
            i = pi[i-1];
        if( A[i] == B[j] )
            i++;

        if( i == strlen(A) )
        {
            i = pi[i-1];
            pos[++n] = j-strlen(A)+1;
        }
    }
    out<<n<<'\n';
    for( int j = 1; j<=n; j++ )
        out<<pos[j]<<' ';
    out<<'\n';
    return 0;
}