Cod sursa(job #3005611)

Utilizator razvanalexrotaruRazvan Alexandru Rotaru razvanalexrotaru Data 17 martie 2023 09:33:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int tata[2000008],lg1,lg2,i2,i,aux,cnt;
char cuv1[2000008],cuv2[2000008];
vector<int>ras;
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fin>>cuv1;
    lg1=strlen(cuv1);
    fin>>cuv2;
    lg2=strlen(cuv2);
    tata[0]=-1;
    for(i=1;i<lg1;i++)
    {
        i2=i-1;
        while(cuv1[tata[i2]+1]!=cuv1[i] && i2!=-1)
        {
            i2=tata[i2];
        }
        if(i2==-1)
            tata[i]=-1;
            else
            tata[i]=tata[i2]+1;
    }
    aux=-1;
    for(i=0;i<lg2;i++)
    {
        while(cuv1[aux+1]!=cuv2[i] && aux!=-1)
        {
            aux=tata[aux];
        }
        if(cuv1[aux+1]==cuv2[i])
        {
            aux=aux+1;
        }
        if(aux>=lg1-1)
        {
            cnt++;
            if(cnt<=1000)
                ras.push_back(i-lg1+1);
        }
    }
    fout<<cnt<<'\n';
    for(auto i: ras)
    {
        fout<<i<<" ";
    }
    return 0;
}