Cod sursa(job #2366639)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 4 martie 2019 21:19:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda pregatire_cls12_oji Marime 0.93 kb
#include <bits/stdc++.h>



using namespace std;

const int NMAX = 2e6 + 5;

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 = -1;

    for(i = 0; i < b.size(); i++)

    {

        while(idx > -1 and b[i] != a[idx + 1])idx = g[idx];

        if(b[i] == a[idx + 1]) idx++;

        if(idx == a.size() - 1)ans.push_back(i - idx) , idx = g[ idx ];;





    }

    fout << ans.size() << "\n";

    for(i = 0; i < min(int(ans.size()) , 1000); i++)

        fout << ans[i] << " ";

    return 0;

}