Cod sursa(job #841018)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 23 decembrie 2012 17:22:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 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);
    scanf("%s",A+1);
    scanf("%s",B+1);
    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;
}