Cod sursa(job #1110940)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 18 februarie 2014 15:10:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int LMAX = 2000000+2;
const int SMAX = 1000;

int LA,LB,top;
int S[SMAX+2];
char A[LMAX];
char B[LMAX];
int Pi[LMAX];

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

void KMP()
{
    int i,q=0;
    for(i=1; i<=LB; i++)
    {
        while(q && A[q+1]!=B[i]) q=Pi[q];
        if(A[q+1]==B[i]) q++;
        if(q==LA)
        {
            top++;
            if(top<=SMAX) S[top]=i-q;
            q=Pi[q];
        }
    }
}

int main()
{
    int i;

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

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

    LA=strlen(A+1);
    LB=strlen(B+1);

    Prefix();
    KMP();

    printf("%d\n",top);
    for(i=1; i<=min(top,SMAX); i++)
        printf("%d ",S[i]);

    return 0;
}