Cod sursa(job #2469365)

Utilizator hunting_dogIrimia Alex hunting_dog Data 6 octombrie 2019 20:25:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <iostream>

#define NMAX 2000001

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char a[NMAX],b[NMAX];
int lp[NMAX]={0};

void make_prefix(char *v,int *lps)
{
    int len=0,i=1;
    lps[0]=0;
    while(v[i]!='\00')
    {
        if(v[i]==v[len])
        {
            ++len;
            lps[i]=len;
            ++i;
        }
        else
        {
            if(len)
                len=lps[len-1];
            else
            {
                lps[i]=0;
                ++i;
            }
        }
    }
}

int main()
{
    f.getline(a,NMAX,'\n');
    f.getline(b,NMAX,'\n');
    make_prefix(a,lp);
    int i=0,j=0,nr=0,v[1000];
    while(b[j]!='\00')
    {
        if(a[i]==b[j])
        {
            ++i;
            ++j;
        }
        if(a[i]=='\00')
        {
            v[nr++]=j-i;
            if(nr==1000)
                break;
            i=lp[i-1];
        }
        else if(b[j]!='\00' && a[i]!=b[j])
        {
            if(i)
                i=lp[i-1];
            else
                ++j;
        }
    }
    g<<nr<<'\n';
    for(i=0;i<nr;++i)
        g<<v[i]<<' ';
    return 0;
}