Cod sursa(job #390335)

Utilizator cristiprgPrigoana Cristian cristiprg Data 3 februarie 2010 15:49:10
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <cstring>
#define DIM 2000005

int T[DIM], L1, L2, count, sol[1001];
char S[DIM], W[DIM];

void KMP()
{
    T[0] = -1;
    T[1] = 0;
    int pos = 2, cnd = 0;
    while (pos < L1)
        if (W[pos - 1] == W[cnd])
            T[pos] = ++cnd, ++pos;
        else
            if (cnd > 0)
                cnd = T[cnd];
            else
                T[pos] = 0, ++pos;

    int m = 0, i = 0;
    while (m + i < L2)
        if (W[i] == S[m + i])
        {
            ++i;
            if (i == L1)
            {
                ++count;
                if (count <= 1000)
                    sol[count] = m;
            }
        }
        else
        {
            m += i - T[i];
            if (T[i] > -1)
                i = T[i];
            else
                i = 0;
        }

}

int main()
{
    FILE *f = fopen("strmatch.in", "r");
    fscanf(f, "%s%s", W, S);
    fclose(f);
    L1 = strlen(W);
    L2 = strlen(S);
    KMP();
    f = fopen("strmatch.out", "w");
    fprintf (f, "%d\n", count);
    for (int i = 1; i <= ((count>1000)?1000:count); ++i)
        fprintf (f, "%d ", sol[i]);
    fclose(f);
    return 0;
}