Pagini recente » Monitorul de evaluare | Cod sursa (job #791241) | Cod sursa (job #1612876) | Cod sursa (job #704645) | Cod sursa (job #454934)
Cod sursa(job #454934)
#include<stdio.h>
#include<string.h>
#define MAX 2000005
char a[MAX], b[MAX];
long v[MAX],n,m;
void prefix()
{
int k,q;
v[1]=0;
k=0;
for(q=2;q<=m;q++)
{
while (k>0 && a[k+1]!=a[q]) k=v[k];
if (a[k+1]==a[q]) k++;
v[q]=k;
}
}
int main()
{
FILE *f=fopen("strmatch.in","rt");
FILE *g=fopen("strmatch.out","wt");
fgets(a,MAX,f);
fgets(b,MAX,f);
m=strlen(a)-1;
n=strlen(b)-1;
long i;
for(i=m;i>=1;i--) a[i]=a[i-1];
for(i=n;i>=1;i--) b[i]=b[i-1];
a[0]=' ';
b[0]=' ';
prefix();
long q;
long ls=0,s[MAX];
q=0;
for (i=1;i<=n;i++)
{
while (q>0 && a[q+1]!=b[i]) q=v[q];
if (a[q+1]==b[i]) q++;
if (q==m)
{ls++;
if (ls<=1000)
{
s[ls]=i-m;}
q=v[q];
}
}
fprintf(g,"%li\n",ls);
for (i=1;i<=ls;i++)
fprintf(g,"%li ",s[i]);
fclose(f);
fclose(g);
return 0;
}