Cod sursa(job #2985242)

Utilizator razvanalexrotaruRazvan Alexandru Rotaru razvanalexrotaru Data 25 februarie 2023 23:37:40
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
#include <fstream>
#define cin fin
#define cout fout
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int lg1,j,i,tata[2000008],aux,ras[2000008],cnt,poz,lg2;
char cuv1[2000008],cuv2[2000008];
int main()
{
    cin>>cuv1+1;
    lg1=strlen(cuv1+1);
    aux=0;
    tata[1]=0;
    for(i=2;i<=lg1;i++)
    {
        j=tata[i-1];
        while(cuv1[j+1]!=cuv1[i] && j!=0)
        {
            j=tata[j];
        }
        if(cuv1[j+1]==cuv1[i])
        tata[i]=j+1;
        else
        tata[i]=0;
    }
    poz=0;
    cin>>cuv2+1;
    lg2=strlen(cuv2+1);
    for(i=1;i<=lg2;i++)
    {
        while(cuv2[i]!=cuv1[poz+1] && poz!=0)
        {
            poz=tata[poz];
        }
        if(cuv2[i]=cuv1[poz+1])
            poz++;
        if(poz==lg1)
        {
            ras[++cnt]=i-lg1;
        }
    }
    cout<<cnt<<'\n';
    for(i=1;i<=min(1000,cnt);i++)
    {
        cout<<ras[i]<<" ";
    }
    return 0;
}