Cod sursa(job #2098725)

Utilizator NaritaandreiCNAINarita Andrei NaritaandreiCNAI Data 3 ianuarie 2018 14:14:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
FILE *f,*g;
char x[2000004],y[2000004];
int pi[2000004],v[1002];
int main()
{
    int i,k,m,n,nr=0;
    f=fopen("strmatch.in","r");
    g=fopen("strmatch.out","w");
    fgets(x+1,2000002,f);
    fgets(y+1,2000002,f);
    m=strlen(x+1)-1;
    n=strlen(y+1)-1;
    k=0;
    for(i=2;i<=m;i++)
    {
        while(k>0 && x[i]!=x[k+1])
            k=pi[k];
        if(x[k+1]==x[i])
            k++;
        pi[i]=k;
    }
    k=0;
    for(i=1;i<=n;i++)
    {
        while(k>0 && y[i]!=x[k+1])
            k=pi[k];
        if(y[i]==x[k+1])
            k++;
        if(k==m)
        {
            nr++;
            if(nr<1000)
                v[nr]=i-m;
        }
    }

    fprintf(g,"%d\n",nr);
    if(nr>1000)
        nr=1000;
    for(i=1;i<=nr;i++)
        fprintf(g,"%d ",v[i]);
    fclose(f);
    fclose(g);
    return 0;
}