Cod sursa(job #678102)

Utilizator wefgefAndrei Grigorean wefgef Data 11 februarie 2012 00:21:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <cassert>
#include <cstdio>
#include <cstring>

#include <vector>
using namespace std;

const int MAX_N = 2000005;
const int MAX_SOL = 1000;

char text[MAX_N];
char pattern[MAX_N];
int prefix[MAX_N];

void read() {
    assert(freopen("strmatch.in", "r", stdin));
    assert(freopen("strmatch.out", "w", stdout));

    assert(scanf("%s", pattern + 1) == 1);
    assert(scanf("%s", text + 1) == 1);
}

void compute_prefix(char* pattern) {
    int n = strlen(pattern + 1);

    int p = 0;
    prefix[1] = 0;
    for (int i = 2; i <= n; ++i) {
        while (p > 0 && pattern[p + 1] != pattern[i])
            p = prefix[p];
        if (pattern[p + 1] == pattern[i])
            ++p;
        prefix[i] = p;
    }
}

vector<int> pattern_match(char* text, char* pattern) {
    int n = strlen(text + 1), m = strlen(pattern + 1);
    vector<int> matches;

    int p = 0;
    for (int i = 1; i <= n; ++i) {
        while (p > 0 && text[i] != pattern[p + 1])
            p = prefix[p];
        if (text[i] == pattern[p + 1])
            ++p;
        if (p == m) {
            if (matches.size() < static_cast<unsigned>(MAX_SOL))
                matches.push_back(i - m);
            p = prefix[p];
        }
    }

    return matches;
}

void write(vector<int> v) {
    printf("%d\n", v.size());
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        printf("%d ", *it);
}

int main() {
    read();
    compute_prefix(pattern);
    write(pattern_match(text, pattern));
}