Cod sursa(job #2883896)

Utilizator PescaPescariu Matei Alexandru Pesca Data 1 aprilie 2022 22:47:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int const N=(int)1e6*2+7;
char txt[N],f[N];
int ps[N];
int n,m;
void prefix()
{
    ps[0]=0;
    int j=0;
    for(int i=1;i<n;i++)
    {
        while(j && f[j]!=f[i])
            j=ps[j-1];
        if(f[j]==f[i])
        {
            j++;
            ps[i]=j;
        }
        else
            ps[i]=0;
        ///cout<<ps[i]<<' ';
    }
}
int R[N];
void solve()
{
    int j=0,r=0;
    for(int i=0;i<m;i++)
    {
        if(j==n)
        {
            R[r++]=i-j;
            j=ps[j-1];
        }
        while(j && f[j]!=txt[i])
            j=ps[j-1];
        if(txt[i]==f[j])
            j++;
    }
    if(j==n)
        R[r++]=m-j;
    fout<<r<<'\n';
    r=min(r,1000);
    for(int i=0;i<r;i++)
        fout<<R[i]<<' ';
}
int main()
{
    fin>>f>>txt;
    n=strlen(f);
    m=strlen(txt);
    prefix();
    solve();
}