Cod sursa(job #2365397)

Utilizator AplayLazar Laurentiu Aplay Data 4 martie 2019 13:25:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>
#include <cstring>

#define LENGTH_MAX 2000010

char pattern[LENGTH_MAX], text[LENGTH_MAX];
int prefix[LENGTH_MAX], numberOfSolutions = 0, solutions[LENGTH_MAX];

void doPrefix(char* pattern, int length, int* prefix) {
    int it = 1, k = 0;
    prefix[0] = 0;
    while (it < length) {
        if (pattern[it] == pattern[k]) {
            prefix[it] = ++k;
            ++it;
        } else {
            if (0 < k) {
                k = prefix[k - 1];
            } else {
                k = prefix[it] = 0;
                ++it;
            }
        }
    }
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s\n%s", pattern, text);

    int patternLength = strlen(pattern);
    int textLength = strlen(text);

    doPrefix(pattern, patternLength, prefix);

    int it = 0, jt = 0;
    while (jt < textLength) {
        if (pattern[it] == text[jt]) {
            ++it;
            ++jt;
        }

        if (it == patternLength) {
            solutions[numberOfSolutions++] = jt - it;
            it = prefix[patternLength - 1];
        } else if (pattern[it] != text[jt]) {
            if (0 == it) {
            ++jt;
            } else {
                it = prefix[it - 1];
            }
        }
    }

    printf("%d\n", numberOfSolutions);
    for (int it = 0; it < numberOfSolutions; ++it) {
        printf("%d ", solutions[it]);
    }

    return 0;
}