Cod sursa(job #2366312)

Utilizator racheriunicolaechowchow racheriunicolae Data 4 martie 2019 19:29:37
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 2e6;
int g[NMAX];
string a , b;
void precalc()
{
    int st;
    g[0] = -1;
    st = -1;
    for(int i = 1; i < a.size(); i++)
    {
        while(st > -1 and a[i] == a[st + 1])st = g[st];
        if(a[i] == a[st + 1])st++;
        g[i] = st;
    }
}
int idx , i;
vector < int > ans;
int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin >> a >> b;
    precalc();
    idx = 0;
    for(i = 0; i < b.size(); i++)
    {
        while(b[i + idx] == a[idx])idx++;
        if(idx == a.size())ans.push_back(i);
        idx = g[idx] + 1;
    }
    fout << ans.size() << "\n";
    for(i = 0; i < ans.size(); i++)
        fout << ans[i] << " ";
    return 0;
}