Cod sursa(job #3142262)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 20 iulie 2023 13:28:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int n,m;
char pat[2000005];
char v[2000005];
int l[2000005];

int sol[5000];
int ksol;


int pat_l;
int t_l;

void prec_l()
{
    int j=0;
    int i=1;

    while(i<pat_l)
    {
        if(pat[i]==pat[j])
        {
            j++;
            l[i]=j;
            i++;
        }
        else
        {
            if(j!=0)
                j=l[j-1];
            else
                l[j]=0,i++;
        }


    }
}

int main()
{
    fin>>pat;
    fin>>v;
    pat_l = strlen(pat);
    t_l = strlen(v);
    prec_l();

    /**for(int i=0; i<pat_l; i++)
    {
        fout<<l[i]<<' ';
    }**/

    int i=0;
    int j = 0;

    while (i<t_l)
    {
        if(v[i]==pat[j])
        {
            i++;
            j++;
        }
        if(j==pat_l)
        {
            ksol++;
            if(ksol<=1000)
                sol[ksol]=i-j;
            j=l[j-1];
        }
        else if(i <t_l && pat[j]!=v[i])
        {
            if(j!=0)
                j=l[j-1];
            else
                i++;
        }
    }

    fout<<ksol<<'\n';
    for(int i=1;i<=min(ksol,1000);i++)
        fout<<sol[i]<<' ';

}