Cod sursa(job #3293676)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 12 aprilie 2025 11:40:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
#define INF 2000000000
#define VMAX 4000005
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int mod = 2000003;
string a,b;
int lg[VMAX];
vector<int> pozitii;


int main()
{
    int n,m,i,j,k,t,q,nr,minim,maxim,suma,lungime_a;
    fin>>a>>b;
    lungime_a=a.size();
    a+='#';
    a+=b;

    for(i=1;i<a.size();i++)
    {
        j=lg[i-1];
        while(j>0 && a[j]!=a[i])
            j=lg[j-1];

        if(a[j]==a[i])
            j++;
        lg[i]=j;

        if(lg[i]>=lungime_a)
            pozitii.push_back(i-2*lungime_a);
    }

    fout<<pozitii.size()<<'\n';
    for(i=0;i<min(1000,(int)pozitii.size());i++)
        fout<<pozitii[i]<<' ';
    fout<<'\n';



    return 0;
}