Cod sursa(job #2187383)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 26 martie 2018 14:40:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

int cnt;
string a, b;
vector < int > phi, ans;

void compute_phi(string s) {
    phi = vector < int > ((int)s.size(), 0);

    int k = 0;
    for (int i = 2; i < (int)s.size(); ++i) {
        while (k && s[k+1] != s[i])
            k = phi[k];
        if (s[k+1] == s[i]) k++;

        phi[i] = k;
    }
}

void compute_ans(string S, string s) {
    int k = 0;
    for (int i = 1; i < (int)S.size(); ++i) {
        while (k && s[k+1] != S[i])
            k = phi[k];
        if (s[k+1] == S[i]) k++;

        if (k == (int)s.size() - 1) {
            cnt++;
            if (cnt <= 1000)
                ans.push_back(i - k);
        }
    }
}

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

    ios_base :: sync_with_stdio(false);

    cin >> a >> b;
    a = ' ' + a; b = ' ' + b;

    compute_phi(a);
    compute_ans(b, a);

    cout << cnt << '\n';
    for (auto &it: ans)
        cout << it << ' ';

    return 0;
}