Cod sursa(job #3141551)

Utilizator AnaGrigorieAna Teodora Grigorie AnaGrigorie Data 14 iulie 2023 15:33:19
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
/**
 * avem un text cu lungimea m<=100 000 si un cuv de lungime n<=100 000
 * cuv poate fi oricat de lungime
 * det toate aparitiile cuv in text ca secv
**/
#include <fstream>
#include <cstring>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001],b[2000001];
int sol[1001],p[2000001],n,m,L,k;
int main()
{
    fin>>a+1>>b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    //KMP=knuth-moris-pratt --> obtine timp de calcul liniar : n+m
    //pas 1: facem o preprocesare pe cuv a si dupa vom construi pt fiecare poz i din a o val p[i]
    // p[i] = lungimea maxima a unui sufix terminat la poz i care e totodata si prefix
    L=0;
    for(int i=2;i<=n;i++)
    {
        while(L!=0 && a[i]!=a[L+1])
        {
            L=p[L];
        }
            if(a[i]==a[L+1])
            {
                L++;
            }
            p[i]=L;
    }
    L=0;
    for(int i=1;i<=m;i++)
    {
        while(L!=0 && b[i]!=a[L+1])
        {
            L=p[L];
        }
        if(b[i]==a[L+1])
        {
            L++;
        }
        if(L==n)
        {
            k++;
            if(k<=1000)
            {
                sol[k]=i-n+1;//cu indexare de la 1
            }
            L=p[L];
        }
    }
    fout<<k<<"\n";
    if(k>1000)
    {
        k=1000;
    }
    for(int i=1;i<=k;i++)
    {
        fout<<sol[i]-1<<" ";
    }
    return 0;
}