Cod sursa(job #1457664)

Utilizator TrixerAdrian Dinu Trixer Data 3 iulie 2015 23:26:48
Problema Potrivirea sirurilor Scor 18
Compilator c Status done
Runda Arhiva educationala Marime 1.49 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXL 2000000

int w_len, s_len, last, t[MAXL], n[1000], N;
char w[MAXL], s[MAXL];

int main()
{
    int i, j;

    // open files
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    // read strings
    scanf("%[^\n]", w); getchar();
    scanf("%[^\n]", s); getchar();

    w_len = strlen(w);
    s_len = strlen(s);

    // bake partial match table
    t[0] = -1;
    i = 2;

    while (i < w_len)
    {
        if (w[i - 1] == w[last])
        {
            last++;
            t[i] = last;
            i++;
        }
        else if (last > 0)
        {
            last = t[last];
        }
        else
        {
            t[i] = 0;
            i++;
        }
    }
/*
    for (i = 0; i < w_len; i++)
    {
        printf("%d", t[i]);
    }
*/
    // search for matches
    i = 0;
    j = 0;

    while (i + j < s_len)
    {
        if (w[j] == s[i + j])
        {
            if (j == w_len - 1)
            {
                if (N < 1000) n[N] = i;
                N++;
            }
            j++;
        }
        else
        {
            if (t[j] > -1)
            {
                i += j - t[j];
                j = t[j];
            }
            else
            {
                j = 0;
                i++;
            }
        }
    }

    // print results
    printf("%d\n", N);
    for (i = 0; i < N; i++)
    {
        printf("%d ", n[i]);
    }

    return 0;
}