Cod sursa(job #2545018)

Utilizator sandifx68Fazakas Alexandru sandifx68 Data 12 februarie 2020 19:23:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

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

    int i=1,j=0,lp,l[2000001],ls,nr=0,k=0,v[2000001];
    char s[2000001],p[2000001];
int main()
{
    fin>>p>>s;
    lp=strlen(p);
    ls=strlen(s);
    l[0]=0;
    while(i<lp)
    {
        if(p[i]==p[j])
        {
            j++;l[i]=j;i++;
        }
        else
            if(j==0) l[i++]=0;
        else j=l[j-1];
    }
    i=0;j=0;
    while(i<ls)
    {
        if(s[i]==p[j])
        {
            i++;j++;
            if(j==lp)
            {
                nr++;
                v[++k]=i-j;
                j=l[j-1];
            }
        }
        else
            if(j==0)
            i++;
        else j=l[j-1];
    }
    fout<<nr<<"\n";
    for(i=1;i<=k;i++)
        fout<<v[i]<<" ";
}