Cod sursa(job #841017)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 23 decembrie 2012 17:21:44
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<cstdio>
#include<cstring>
#define LMAX 2000000+10
using namespace std;
char A[LMAX],B[LMAX];
int LA,LB,pi[LMAX],top,st[1010];
void prefix() //Calculam prefixele = sufixele de lungime maxima pana la pozitia i a sirului A (si diferite de sirul in sine)
{
    int q=0,i;
    for(i=2;i<=LA;i++)
    {
        for(;q;)
        {
            if(A[q+1]==A[i]) break;
            else q=pi[q];
        }
        if(A[q+1]==A[i]) q++;
        pi[i]=q;
    }
}
void potrivire() //Potrivim prefixele lui A cu sirul B pana gasim A inclus in B => adaugam in stiva de solutii
{
    int i,q=0;
    for(i=1;i<=LB;i++)
    {
        for(;q;)
        {
            if(B[i]==A[q+1]) break;
            else q=pi[q];
        }
        if(B[i]==A[q+1]) q++;
        if(q==LA)
        {
            top++;
            if(top<=1000) st[top]=i-q;
            q=pi[q];
        }
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(A+1,LMAX,stdin);
    fgets(B+1,LMAX,stdin);
    LA=strlen(A+1);
    LB=strlen(B+1);
    prefix();
    potrivire();
    printf("%d\n",top); top=top<1000?top:1000;
    for(int i=1;i<=top;i++) printf("%d ",st[i]);
    return 0;
}