Cod sursa(job #2199985)

Utilizator MaligMamaliga cu smantana Malig Data 29 aprilie 2018 20:30:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;

#if 1
    #define pv(x) out<<#x<<" = "<<(x)<<"; ";cout.flush()
    #define pn out<<endl
#else
    #define pv(x)
    #define pn
#endif

#ifdef INFOARENA
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
#else
    #define in cin
    #define out cout
#endif

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 3e6 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
using zint = int;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);

    string patt,str;
    in >> patt >> str;
    int N = patt.length(), M = str.length();
    vector<int> pf(N,0);
    int k = 0;
    for (int i = 1;i < N;++i) {
        while (patt[i] != patt[k] && k > 0) {
            k = pf[k];
        }

        if (patt[i] == patt[k]) {
            ++k;
        }

        pf[i+1] = k;
        // pv(i);pv(pf[i+1]);pn;
    }

    vector<int> sol;
    k = 0;
    for (int i = 0;i < M;++i) {
        while (str[i] != patt[k] && k > 0) {
            k = pf[k];
        }

        if (str[i] == patt[k]) {
            ++k;
            if (k == N) {
                sol.pb(i - N + 1);
                k = pf[k];
            }
        }
    }

    // pv(sol.size()); pn;
    out << sol.size() << '\n';
    if (sol.size() > 1000) {
        sol.resize(1000);
    }

    for (int val : sol) {
        out << val << ' ';
    }

    out.flush();
    return 0;
}