Cod sursa(job #2231544)

Utilizator roberttrutaTruta Robert roberttruta Data 14 august 2018 21:05:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <cstring>
using namespace std;
int n,m,i,j,nr,v[2000002],afis[1002];
char c[2000002], p[2000002];
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    f.get(c,2000002);
    f.get();
    f.get(p,2000002);
    n=strlen(c);
    m=strlen(p);

///construim prefix : (v[x]=cel mai lung prefix pana la poz x care e si sufix)
    for(i=1; i<n; i++)
    {
        while(c[j]!=c[i] && j>0)
            j=v[j-1];
        if(c[j]==c[i])
        {
            v[i]=j+1;
            j++;
        }
    }
///
j=0;
    for(i=0; i<m; i++)
    {
        while(p[i]!=c[j] && j>0)
            j=v[j-1];
        if(p[i]==c[j])
        {
            if(j==n-1)
            {
            if(nr<=999)
                afis[++nr]=i-n+1;
            else
                nr++;
            }
            j++;
        }
    }
    g<<nr<<'\n';
    nr=min(nr,1000);
    for(i=1;i<=nr;i++)
        g<<afis[i]<<' ';

    return 0;
}