Cod sursa(job #1389906)

Utilizator raztaapDumitru raztaap Data 16 martie 2015 18:45:55
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <cstring>
#define NMAX  2000005
#define minim(a,b) a<b?a:b
using namespace std;
int n, m;
int urm[NMAX],pos[NMAX], nr;
char T[NMAX], P[NMAX];
void citire()
{
    gets(P);
    gets(T);
    m=strlen(P);
    n=strlen(T);
}
void make_prefix(char *P)
{
    int k=-1, x;
    urm[0]=0;
    for(x=1;x<m;++x)
    {
        while(k>=0&&P[k+1]!=P[x])
            k=urm[k];
        if(P[k+1]==P[x])
            ++k;
        urm[x]=k;
    }
}
void KMP()
{
    make_prefix(P);
    int i, x=-1;
    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)
                pos[nr]=i-m+1;
            x=urm[x];
        }
    }
}
void afisare()
{
    int i;
    int POZ=minim(nr, 1000);
    printf("%d\n", nr);
    for(i=1;i<=POZ;++i)
        printf("%d ", pos[i]);
    printf("\n");
}
void rezolva_problema()
{
    citire();
    KMP();
    afisare();
}
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    rezolva_problema();
    return 0;
}