Cod sursa(job #1265356)

Utilizator dica69Alexandru Lincan dica69 Data 17 noiembrie 2014 10:25:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <cstring>

using namespace std;

FILE *f1,*f2;
long n,m,i,q,k,urm[2000005],sol[2000005],nr;
char p[2000005],t[2000005];

int main()
{f1 = fopen("strmatch.in","r");
f2 = fopen("strmatch.out","w");
fgets(p,2000006,f1);
fgets(t,2000006,f1);
m=strlen(p)-1;
n=strlen(t)-1;
if (m>n) nr=0;
else
{k=0;
for (q=1;q<m;q++)
{while (k>0 && p[k]!=p[q]) k=urm[k-1];
if (p[k]==p[q]) k++;
urm[q]=k;
}
q=0;
for (i=0;i<n;i++)
{while (q>0 && p[q]!=t[i]) q=urm[q-1];
if (p[q]==t[i]) q++;
if (q==m) sol[++nr]=i-m+1;
}
}
fprintf(f2,"%ld\n",nr);
if (nr>1000) nr=1000;
for (i=1;i<=nr;i++) fprintf(f2,"%ld ",sol[i]);

fclose(f1);fclose(f2);
    return 0;
}

//Challenges are what make life interesting and overcoming them is what makes life meaningful.