Cod sursa(job #678104)

Utilizator wefgefAndrei Grigorean wefgef Data 11 februarie 2012 00:22:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 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) {
            matches.push_back(i - m);
            p = prefix[p];
        }
    }

    return matches;
}

void write(vector<int> v) {
    printf("%d\n", v.size());
    for (int i = 0; i < MAX_SOL && i < (int)v.size(); ++i)
        printf("%d ", v[i]);
}

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