Cod sursa(job #1946952)

Utilizator ana-maria.simiAna-Maria Simionescu ana-maria.simi Data 30 martie 2017 17:09:59
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#define minim(a, b) ((a < b) ? a : b)
#include <fstream>
#include <cstring>
int Urm[2000001],n,m,sol[1001],nr;
char T[2000005],P[2000005];

void initurm()
{
    int i,k=0;

    for(i= 2, Urm[1]=0; i<=m; i++)
    {
        while(k && P[k+1]!=P[i])
            k=Urm[k];
        if(P[k+1]==P[i])
            k++;
        Urm[i]=k;
    }
}


int main()
{int i, x=-1;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(P, sizeof(P), stdin);
fgets(T, sizeof(T), stdin);
n=strlen(T);
m=strlen(P);
for(i=m; i>=1; i--)
    P[i]=P[i-1];
P[0]=' ';
for(i=n; i>=1; i--)
    T[i]=T[i-1];
T[0]=' ';
initurm();
for(i=0; i<n; i++)
{
    while(x>0 && P[x+1]!=T[i])
        x=Urm[x];
    if(P[x+1]==T[i])
        x++;
    if(x==m-1)
        {nr++;
        if(nr<=1000)
            sol[nr]=i-m+1;
        x=Urm[x];}
}

for(i=1; i<=n; i++)
    { while(x &&  P[x+1]!=T[i])
            x=Urm[x];
    if(P[x+1]==T[i])
        x++;
    if(x==m)
        {
            x=Urm[m];
            nr++;
            if (nr<= 1000)
                sol[nr]=i-m;
        }
    }

printf("%d\n", nr);
nr=minim(nr,1000);
for(i=1; i<=nr; i++)
    printf("%d ", sol[i]);
    return 0;
}