Cod sursa(job #1218721)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 12 august 2014 13:07:19
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
char A[2000005],B[2000005];
int N,M,P[2000005],ap;
vector<int> pos;

void read( void )
{
    scanf("%s%s",A + 1, B + 1);
    A[0] = B[0] = '#';
    N = strlen(A + 1);
    M = strlen(B + 1);
}

void make_prefix( void )
{
    int i,q = 0;
    for(int i = 2; i <= N; ++i)
    {
        while(q && A[i] != A[q+i])
            q = P[q];
        q += (A[i] == A[q+1]);
        P[i] = q;
    }
}

void make_match( void )
{
    int i,q = 0;
    for(int i = 1; i <= M; ++i)
    {
        while(q && B[i] != A[q + 1])
            q = P[q];
        q += (B[i] == A[q+1]);
        if(q == N)
        {
            ++ap;
            if(pos.size() < 1000)
                pos.push_back( i - N );
            q = P[q];
        }
    }
}

void afish( void )
{
    printf("%d\n",ap);
    for(vector<int>::iterator it = pos.begin(); it != pos.end(); ++it)
        printf("%d ",*it);
}

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

    read();
    make_prefix();
    make_match();
    afish();

    return 0;
}