Pagini recente » Cod sursa (job #1987726) | Cod sursa (job #1910730) | Cod sursa (job #3131663) | Cod sursa (job #68085) | Cod sursa (job #520837)
Cod sursa(job #520837)
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
int m,n,p,k,i,rez,q,t;
long L[2000005],REZ[2000001];;
char A[2000005],B[2000005];
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;
}