Cod sursa(job #934753)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 31 martie 2013 12:56:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <cstdio>
#include <cstring>
#include <cassert>

#include <algorithm>
#include <vector>

using namespace std;

const int MAX_N = 2000005;

int N, M, Z[MAX_N], MatchCount;
char Pattern[MAX_N], String[MAX_N];
vector<int> MatchPositions;

void BuildZ() {
    Z[1] = 0;
    for (int i = 2, p = 1, right = 1; i <= N; ++i) {
        if (right >= i)
            Z[i] = min(right - i + 1, Z[i - p + 1]);
        for (; i + Z[i] <= N && Pattern[Z[i] + 1] == Pattern[i + Z[i]]; ++Z[i]);
        if (i + Z[i] - 1 > right) {
            p = i;
            right = i + Z[i] - 1;;
        }
    }
}

void ZAlgorithm() {
    BuildZ();
    for (int i = 1, p = 0, right = 0; i <= M; ++i) {
        int LCP = 0;
        if (right >= i)
            LCP = min(right - i + 1, Z[i - p + 1]);
        for (; LCP < N && i + LCP <= M && Pattern[LCP + 1] == String[i + LCP]; ++LCP);
        if (i + LCP - 1 > right) {
            p = i;
            right = i + LCP - 1;
        }
        if (LCP == N) {
            ++MatchCount;
            if (MatchCount <= 1000)
                MatchPositions.push_back(i - 1);
        }
    }
}

void Read() {
    assert(freopen("strmatch.in", "r", stdin));
    assert(scanf("%s\n%s", Pattern + 1, String + 1) == 2);
    N = strlen(Pattern + 1);
    M = strlen(String + 1);
}

void Print() {
    assert(freopen("strmatch.out", "w", stdout));
    printf("%d\n", MatchCount);
    for (size_t i = 0; i < MatchPositions.size(); ++i)
        printf("%d ", MatchPositions[i]);
    printf("\n");
}

int main() {
    Read();
    ZAlgorithm();
    Print();
    return 0;
}