Cod sursa(job #1415548)

Utilizator gallexdAlex Gabor gallexd Data 5 aprilie 2015 00:23:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
#include <cstring>

char pattern[2000100], text[2000100];
int table[2000100], positions[1010];
int pattern_length, text_length, number_of_matches;

void prefix() {
    table[0] = 0;
    int match=0;
    for (int i=1; i<pattern_length; ++i) {
        while (match>0 && pattern[match] != pattern[i])
            match = table[match-1];
        if (pattern[match] == pattern[i])
            ++match;
        table[i] = match;
    }
}

void kmp() {
    int match = 0;
    for (int i=0; i<text_length; ++i) {
        while (match>0 && pattern[match] != text[i])
            match = table[match-1];
        if (pattern[match] == text[i])
            match++;

        if (match == pattern_length && number_of_matches < 1000)
            positions[number_of_matches++] = i - match + 1;
    }
}

int main () {

    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);

    scanf("%s", pattern);
    scanf("%s", text);
    pattern_length = strlen(pattern);
    text_length = strlen(text);

    prefix();
    kmp();

    printf("%d\n", number_of_matches);
    for (int i=0; i<number_of_matches; ++i)
        printf("%d ", positions[i]);

    return 0;
}