Cod sursa(job #1106271)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 12 februarie 2014 18:05:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include <string.h>

using namespace std;
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");

char s[2000002],ss[2000002];
int k,n,m,urm[2000002],i,q,r[1005],nr;

int main()
{
fgets(s,2000002,f);
strcpy(s+strlen(s)-1,s+strlen(s));
fgets(ss,2000002,f);
strcpy(ss+strlen(ss)-1,ss+strlen(ss));

k=0;
n=strlen(s);
m=strlen(ss);
urm[0]=0;
k=0;
for(i=2;i<=n;i++)
{
while(k>0 && s[k]!=s[i-1])k=urm[k];
if (s[k]==s[i-1])k++;
urm[i]=k;
}
//for(i=1;i<n;i++)
//urm[i]=urm[i]+1;

q=0;
for(i=0;i<m;i++)
{
while (q>0 && s[q]!=ss[i])q=urm[q];
if (s[q]==ss[i])q++;
if (q==n){if (nr<1000)r[++nr]=i-n+1;else nr++;}
}
fprintf(g,"%d\n",nr);
if (nr>1000)nr=1000;
for(i=1;i<=nr;i++)
fprintf(g,"%d ",r[i]);

fclose(g);
return 0;
}