Cod sursa(job #1106261)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 12 februarie 2014 18:01:05
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 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=-1;
for(i=1;i<n;i++)
{
while(k>-1 && s[k+1]!=s[i])k=urm[i-1];
if (s[k+1]==s[i])k++;
urm[i]=k;
}
//for(i=1;i<n;i++)
//urm[i]=urm[i]+1;

q=-1;
for(i=0;i<m;i++)
{
while (q>-1 && s[q+1]!=ss[i])q=urm[q];
if (s[q+1]==ss[i])q++;
if (q==n-1){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;
}