Cod sursa(job #1968129)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 17 aprilie 2017 15:06:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string s, S;
vector < int > phi;

int ans;
vector < int > all;

void input() {
    fin >> s >> S;
    s = ' ' + s; S = ' ' + S;
}

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

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

        phi[i] = k;
    }
}

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

        if (s[k+1] == 0) {
            ans++;
            if (ans <= 1000) all.push_back(i-k);
        }
    }
}

void output() {
    fout << ans << '\n';
    for (auto &it: all) fout << it << ' ';
    fout << '\n';
}

int main() {
    input();
    compute_phi(s);
    compute_answer(S, s);
    output();

    return 0;
}