Cod sursa(job #1996900)

Utilizator AplayLazar Laurentiu Aplay Data 2 iulie 2017 22:19:01
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <stdio.h>
#include <vector>

#define NMAX 2000010
#define minim(a, b) (a < b ? a : b)

using namespace std;

int pi[NMAX], N, M;
string s, t;
vector<int> ans;

void prefix() {
    pi[1] = 0;
    int k = 0;
    for (int it = 2; it <= N; ++it) {
        while (k > 0 && s[k + 1] != s[it]) {
            k = pi[k];
        }
        if (s[k + 1] == s[it]) {
            k += 1;
        }
        pi[it] = k;
    }
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    cin >> s >> t;
    N = s.size();
    M = t.size();
    s = " " + s;
    t = " " + t;

    prefix();

    int q = 0;
    for (int it = 1; it <= M; ++it) {
        while (q > 0 && s[q + 1] != t[it]) {
            q = pi[q];
        }
        if (s[q + 1] == t[it]) {
            q += 1;
        }
        if (N == q) {
            ans.push_back(it);
            q = pi[q];
        }
    }

    cout << ans.size() << endl;
    for (int it = 0; it < minim(1000, ans.size()); ++it) {
        cout << ans[it] - N << " ";
    }

    return 0;
}