Cod sursa(job #2299799)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 10 decembrie 2018 09:40:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

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

constexpr int NMAX=2e6+5;

char A[NMAX], B[NMAX];

int N, M, i, j, PHI[NMAX];

int Sol[NMAX], vf;

void Precalculation ()
{
    strcat(A, "#");
    strcat(A, B);

    N=strlen(A);

    int ans=0;

    for(i=1; i<N; ++i)
    {
        while(ans && A[ans] != A[i])
            ans=PHI[ans-1];

        if(A[ans] == A[i])
            ++ans;

        PHI[i]=ans;
    }
}

void Match ()
{
    for(int i=M+1; i<N; ++i)
        if(PHI[i] == M)
            Sol[++vf]=i-M+1;
}

void Afis ()
{
    g<<vf<<'\n';

    for(int i=1; i<=min(vf, 1000); ++i)
        g<<Sol[i]-M-1<<' ';

    g<<'\n';
}

int main()
{
    f.tie(NULL);

    f>>A>>B;

    M=strlen(A);

    Precalculation();

    Match();

    Afis();

    return 0;
}