Cod sursa(job #2279151)

Utilizator CojocaruVicentiuCojocaru Vicentiu CojocaruVicentiu Data 8 noiembrie 2018 22:54:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
#include<iostream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char p[2000010],t[2000010];
int nrp,nrt,i,j,vt[2000010],vp[2000010],ans,afis;
int main()
{
    fin.get(p,2000010);
    fin.get();
    fin.get(t,2000010);

    nrp=strlen(p);
    nrt=strlen(t);

    i=0;
    for(j=1;j<nrp;j++)
    {
        if(p[i]==p[j])
        {
            i++;
            vp[j]=vp[j-1]+1;
        }
        else
            i=0;
    }
    i=0;
    for(j=0;j<nrt;j++)
    {
        if(p[i]==t[j])
        {
            if(i==nrp-1)
            {
                vt[j-nrp+1]=1;
                ans++;
            }
            i++;
        }
        else
        {
            if(i!=0)
            {
                i=vp[i-1];
                j--;
            }
        }
    }
    fout<<ans<<'\n';
    for(i=0;i<nrt && afis<min(ans,1000);i++)
        if(vt[i]==1)
        {
            fout<<i<<' ';
            afis++;
        }



    fin.close();
    fout.close();
    return 0;
}