Cod sursa(job #1167097)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 4 aprilie 2014 12:47:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int LMAX = 2000000+5;

void Read(),Solve(),Print();

int LA,LB,Nr_Potriviri;
char A[LMAX];
char B[LMAX];
int Pi[LMAX];
int Potriviri[1005];

void Prefix()
{
    int i,q;

    for(i = 2, q = 0; i <= LA; i++)
    {
        while(A[q+1] != A[i] && q) q = Pi[q];
        if(A[q+1] == A[i]) q++;
        Pi[i] = q;
    }
}

void KMP()
{
    int i,q;

    for(i = 1, q = 0; i <= LB; i++)
    {
        while(A[q+1] != B[i] && q) q = Pi[q];
        if(A[q+1] == B[i]) q++;
        if(q == LA)
        {
            Nr_Potriviri++;
            if(Nr_Potriviri <= 1000) Potriviri[Nr_Potriviri] = i - LA;
            q = Pi[q];
        }
    }
}

int main()
{
    Read();
    Solve();
    Print();

    return 0;
}

void Read()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s",A+1);
    scanf("%s",B+1);
}

void Solve()
{
    LA = strlen(A+1);
    LB = strlen(B+1);

    Prefix();
    KMP();
}

void Print()
{
    int i;

    printf("%d\n",Nr_Potriviri);

    for(i = 1; i <= min(1000,Nr_Potriviri); i++)
        printf("%d ",Potriviri[i]);
}