Cod sursa(job #1106427)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 12 februarie 2014 20:05:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <cstdio>

const int LMAX = 2000000, MAXNRREZ = 1000;

int rez [MAXNRREZ + 1];
int prefix [LMAX + 1];
char sC [LMAX + 1];
char s [LMAX + 1];
int nrRez, m, n;

int min2 (int a, int b)
{
    if (a < b)
        return a;

    return b;
}

void setPrefix ()
{
    int i, q = 0;

    for (i = 2; i <= m; i ++)
    {
        while (q != 0 && sC [q + 1] != sC [i])
            q = prefix [q];

        if (sC [q + 1] == sC [i])
            q ++;

        prefix [i] = q;
    }
}

void shift ()
{
    int i;

    for (i = n; i > 0; i --)
        s [i] = s [i - 1];

    for (i = m; i > 0; i --)
        sC[i] = sC [i - 1];

    sC [0] = s [0] = ' ';
}

int lungime (char s [LMAX])
{
    int i = 0;

    while (s [i] != NULL)
        i ++;

    return i;
}

void init ()
{
    freopen ("strmatch.in", "r", stdin);
    freopen ("strmatch.out", "w", stdout);
    gets (sC);
    gets (s);
    n = lungime (s);
    m = lungime (sC);
    shift ();
    setPrefix ();
}

void rezolva ()
{
    int i, q = 0;

    for (i = 1; i <= n; ++i)
    {
        while (q && sC [q + 1] != s [i])
            q = prefix [q];

        if (sC [q + 1] == s [i])
            q ++;

        if (q == m)
        {
            q = prefix [m];
            nrRez ++;

            if (nrRez <= 1000)
                rez [ nrRez] = i - m;
        }
    }
}

void afisare ()
{
    int i, min = MAXNRREZ;

    printf("%d\n", nrRez);

    if (nrRez < min)
        min = nrRez;

    for (i = 1; i <= min; i ++)
        printf ("%d ", rez[i]);
}

int main ()
{
    init ();
    rezolva ();
    afisare ();

    return 0;
}