Cod sursa(job #1165830)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 2 aprilie 2014 23:00:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <cstring>
#include <cassert>

#include <algorithm>
#include <vector>

using namespace std;

const int MAX_N = 4000005;
const int MAX_MATCHES = 1000;

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

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

void Solve() {
    BuildZ();
    for (int i = M + 1; i < N; ++i) {
        if (Z[i] == M) {
            ++MatchCount;
            if (int(Matches.size()) < MAX_MATCHES)
                Matches.push_back(i - M - 1);
        }
    }
}

void Read() {
    assert(freopen("strmatch.in", "r", stdin));
    gets(String);
    M = strlen(String);
    String[M] = '#';
    gets(String + M + 1);
    N = strlen(String);
}

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

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