Cod sursa(job #2634815)

Utilizator PatrascuAdrian1Patrascu Adrian Octavian PatrascuAdrian1 Data 12 iulie 2020 13:31:30
Problema Potrivirea sirurilor Scor 22
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 2e6 + 5;
int pi[Nmax], ans[Nmax];
int N;
string S, C;

void preproc()
{
    int K = 0;
    pi[1] = 0;

    for(int i = 1; i < C.size(); ++i)
    {
        while(K > 0 && C[K] != C[i])
            K = pi[K];

        if(C[K] == C[i])
            K++;

        pi[i] = K;
        //out << pi[i] << " ";
    }
}

void solve()
{
    int K = 0, L = C.size();

    for(int i = 0; i < L; ++i)
    {
        while(K > 0 && S[K] != C[i])
            K = pi[K];

        if(S[K] == C[i])
            K++;

        if(K == S.size())
        {
            if(N <= 1000)
                ans[N++] = (i = i - K + 1);
            i++;
        }
    }

    out << N << '\n';

    for(int i = 0 ; i < N; ++i)
        out << ans[i] << " ";

}

int main()
{
    in >> S >> C;

    preproc();
    solve();
    return 0;
}