Cod sursa(job #3276008)

Utilizator stanciuvalentinStanciu-Tivlea Valentin Gabriel stanciuvalentin Data 12 februarie 2025 12:27:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m,poz[2000200];
char a[2000200],b[2000200];
vector <int> rez;

void prefix()
{
    int k=0;
    poz[1]=0;
    for(int i=2; i<=m; i++)
    {
        while(k and b[k+1]!=b[i])
            k=poz[k];
        if(b[k+1]==b[i])
            k++;
        poz[i]=k;
    }
}

int32_t main()
{
    f>>b>>a, n=strlen(a), m=strlen(b);
    for(int i=n; i>=1; i--)
        a[i]=a[i-1]; a[0]=' ';
    for(int i=m; i>=1; i--)
        b[i]=b[i-1]; b[0]=' ';
    prefix();
    int j=0;
    for(int i=1; i<=n; i++)
    {
        while(j and b[j+1]!=a[i])
            j=poz[j];
        if(a[i]==b[j+1])
            j++;
        if(j==m)
        {
            rez.push_back(i-j);
            if(rez.size()==1000)
                break;
        }
    }
    g<<rez.size()<<'\n';
    for(auto it:rez)
        g<<it<<' ';
    return 0;
}