Cod sursa(job #582299)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 15 aprilie 2011 10:38:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>

using namespace std;

const int N = 2000010;

int n, m, pi[N];

char p[N], t[N];

vector<int> rez;

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

    gets(p + 1);
    gets(t + 1);
}

void init() {
    for (n = 1; p[n]; ++ n);
    -- n;

    for (m = 1; t[m]; ++ m);
    -- m;
}

void calc_pi() {
    int q = 0;

    pi[1] = 0;

    for (int i = 2; i <= n; ++ i) {
        while(q && p[i] != p[q + 1])
            q = pi[q];
        if (p[i] == p[q + 1])
            ++ q;
        pi[i] = q;
    }
}

void solve() {
    int q = 0;

    for (int i = 1; i <= m; ++ i) {
        while(q && t[i] != p[q + 1])
            q = pi[q];
        if (t[i] == p[q + 1])
            ++ q;
        if (q == n) {
            rez.push_back(i - n);
            if (rez.size() == 1000)
                break;
            q = pi[q];
        }
    }
}

void afis() {
    printf("%d\n", rez.size());
    for (int i = 0; i < rez.size(); ++ i)
        printf("%d ", rez[i]);
    printf("\n");
}

int main() {
    read();
    init();
    calc_pi();
    solve();
    afis();
    return 0;
}