Cod sursa(job #2098711)

Utilizator NaritaandreiCNAINarita Andrei NaritaandreiCNAI Data 3 ianuarie 2018 14:04:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
FILE *f,*g;
char x[2000004],y[2000004];
int pi[2000004],d[2000004],v[2000004];
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;
    pi[1]=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++;
        d[i]=k;
    }
    for(i=1;i<=n;i++)
    {
        if(d[i]==m)
            v[++nr]=i-m;
    }
    fprintf(g,"%d\n",nr);
    for(i=1;i<=nr;i++)
        fprintf(g,"%d ",v[i]);
    fclose(f);
    fclose(g);
    return 0;
}