Cod sursa(job #1457951)

Utilizator TrixerAdrian Dinu Trixer Data 5 iulie 2015 01:35:21
Problema Potrivirea sirurilor Scor 18
Compilator c Status done
Runda Arhiva educationala Marime 1.85 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");
        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)
    {
        if (word[j] == string[i + j])
        {
            if (j == word_length - 1)
            {
                if (N < 1000) n[N] = i;
                N++;
            }
            j++;
        }
        else
        {
            if (table[j] > -1)
            {
                i += j - table[j];
                j = table[j];
            }
            else
            {
                j = 0;
                i++;
            }
        }
    }

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

    return 0;
}