Cod sursa(job #1458033)

Utilizator TrixerAdrian Dinu Trixer Data 6 iulie 2015 08:28:45
Problema Potrivirea sirurilor Scor 38
Compilator c Status done
Runda Arhiva educationala Marime 1.9 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXL 2000000

int word_length, string_length, candidate, table[MAXL], n[1000], N;
char word[MAXL], string[MAXL];

int main()
{
    int i, j;

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

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

    word_length     = strlen(word);
    string_length   = strlen(string);
    if (word_length > string_length)
    {
        printf("0\n");
        return 0;
    }

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

    while (i < word_length)
    {
        // match
        if (word[i - 1] == word[candidate])
        {
            candidate++;
            table[i] = candidate;
            i++;
        }
        // fall back
        else if (candidate > 0)
        {
            candidate = table[candidate];
        }
        // mismatch
        else
        {
            table[i] = 0;
            i++;
        }
    }

/*
    // print table
    for (i = 0; i < word_length; i++)
    {
        printf("%d", table[i]);
    }
*/

    // search for matches
    i = 0;
    j = 0;

    while (i + word_length <= string_length)
    {
        // match
        if (word[j] == string[i + j])
        {
            if (j == word_length - 1)
            {
                if (N < 1000) n[N] = i;
                N++;
                i += j - table[j];
            }
            else j++;
        }
        // advance (from table)
        else if (table[j] > -1)
        {
            i += j - table[j];
            j = table[j];
        }
        // advance one position
        else
        {
            j = 0;
            i++;
        }
    }

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

    return 0;
}