Cod sursa(job #1920998)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 10 martie 2017 11:00:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e6 + 10;

string a, b;
int phi[nmax];

int cnt;
vector < int > ans;

void input() {
    cin >> a >> b;
    a = ' ' + a; b = ' ' + b;
}

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

        phi[i] = k;
    }
}

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

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

void output() {
    printf("%d\n", cnt);
    for (auto &it: ans) printf("%d ", it);
}

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

    input();
    compute_phi(a);
    get_ans(a, b);
    output();

    return 0;
}