Cod sursa(job #2391731)

Utilizator Daria09Florea Daria Daria09 Data 29 martie 2019 10:10:43
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
#define dim 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[dim],b[dim];
int pi[dim],pos[1024];
void MakePrefix()
{
    int q=0;
    pi[1]=0;
    for(int i=2;i<=strlen(a+1);++i)
    {
        while(q&a[q+1]!=a[i])
            q=pi[q];
        if(a[q+1]==a[i])
            ++q;
        pi[i]=q;
    }
}
void Solve()
{
    f>>(a+1)>>(b+1);
    MakePrefix();
    int q=0,ans=0;
    for(int i=1;i<strlen(b+1);++i)
    {
        while(q&&a[q+1]!=b[i])
            q=pi[q];
        if(a[q+1]==b[i])++q;
        if(q==strlen(a+1))
        {
            q=pi[q];
            pos[++ans]=i-strlen(a+1);
        }
    }
    g<<ans<<'\n';
    for(int i=1;i<=ans;++i)
        g<<pos[i]<<" ";
}
int main()
{
    Solve();
    return 0;
}