Pagini recente » Cod sursa (job #2761289) | Cod sursa (job #1697853) | Cod sursa (job #855319) | Cod sursa (job #269970) | Cod sursa (job #1265356)
#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.