Pagini recente » Cod sursa (job #1163079) | Cod sursa (job #2099083) | Cod sursa (job #1543652) | Cod sursa (job #1662949) | Cod sursa (job #520832)
Cod sursa(job #520832)
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
long m,n,p,k,i,rez,q,t;
long L[2000000],REZ[2000000];;
char A[2000000],B[2000000];
FILE *fin=fopen("strmatch.in","r");
FILE *fout=fopen("strmatch.out","w");
int main()
{
fscanf(fin,"%s %s",A,B);
fclose(fin);
n=strlen(A);
m=strlen(B);
for (i=n+1;i>=1;i--)
A[i]=A[i-1];
for (i=m+1;i>=1;i--)
B[i]=B[i-1];
L[1]=0;
for (p=2;p<=n;p++)
{
k=L[p-1];
while (k>0 && A[p]!=A[k+1])
k=L[k];
if (A[k+1]==A[p])
k++;
L[p]=k;
}
rez=0;
k=0;
for (t=1;t<=m;t++)
{
while (k>0 && B[t]!=A[k+1])
k=L[k];
if (A[k+1]==B[t])
k++;
if (k==n)
{
rez++;
REZ[rez]=t-k;
}
}
fprintf(fout,"%ld\n",rez);
if (rez>1000)
rez=1000;
for (i=1;i<=rez;i++)
fprintf(fout,"%d ",REZ[i]);
fclose(fout);
return 0;
}