Cod sursa(job #1813744)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 23 noiembrie 2016 11:25:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 2e6 + 10;

string a, str;
int phi[nmax];

int cnt;
vector < int > ans;

void input() {
    fin >> a >> str;
    a = ' ' + a; str = ' ' + str;
}

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

        if (s[k+1] == s[i]) k++;
        phi[i] = k;
    }
}

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

        if (a[k+1] == s[i]) k++;
        if (k == (int)a.size() - 1) {
            cnt++;
            if (cnt <= 1000) ans.push_back(i - (int)a.size() + 1); //0-indexed
        }
    }
}

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

int main()
{
    input();
    compute_phi(a);
    solve(str, a);
    output();

    return 0;
}