Cod sursa(job #2726951)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 21 martie 2021 13:06:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
//Ilie Dumitru
#include<cstdio>
#include<cstring>
#include<queue>

char A[2000005], B[2000005];
int lengthA, lengthB, nrSol;
int pref[2000005];
std::queue<int> apart;

void calcPrefix()
{
    int k=-1, q;
    pref[0]=-1;
    for(q=1;q<lengthA;++q)
    {
        while(A[k+1]!=A[q] && k!=-1)
            k=pref[k];
        if(A[k+1]==A[q])
            ++k;
        pref[q]=k;
    }
}

void solve()
{
    int k=-1, q;
    calcPrefix();
    for(q=0;q<lengthB;++q)
    {
        while(A[k+1]!=B[q] && k!=-1)
            k=pref[k];
        if(A[k+1]==B[q])
            ++k;
        if(k==lengthA-1)
        {
            apart.push(q-k);
            ++nrSol;
            k=pref[k];
        }
    }
    printf("%i\n", nrSol);
    for(;!apart.empty();apart.pop())
        printf("%i ", apart.front());
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    fgets(A, 2000005, stdin);
    fgets(B, 2000005, stdin);
    fclose(stdin);
    lengthA=strlen(A);
    lengthB=strlen(B);
    if(A[lengthA-1]=='\n')
        A[--lengthA]=0;
    if(B[lengthB-1]=='\n')
        B[--lengthB]=0;
    solve();
    fclose(stdout);
    return 0;
}