Pagini recente » Cod sursa (job #37148) | Cod sursa (job #1370500) | Cod sursa (job #197122) | Cod sursa (job #2544352) | Cod sursa (job #160330)
Cod sursa(job #160330)
#include <stdio.h>
#include <string.h>
#define Lmax 2000002
char A[Lmax],B[Lmax];
int L1,L2,i;
int T[Lmax],P[1001],nr;
void citire()
{
freopen("strmatch.in","r",stdin);
scanf("%s",&A);
scanf("%s",&B);
L1=strlen(A);
L2=strlen(B);
}
void prefix()
{
int k,i;
k=-1;
T[0]=-1;
for (i=1;i<L1;++i)
{
while (k>-1 && A[k+1]!=A[i])
k=T[k];
if (A[k+1]==A[i]) ++k;
T[i]=k;
}
}
void match()
{
int k,i;
k=-1;
for (i=0;i<L2;++i)
{
while (k>-1 && A[k+1] != B[i])
k=T[k];
if (A[k+1]==B[i]) ++k;
if (k==L1-1)
{
++nr;
if (nr<=1000) P[nr]=i-L1+1;
}
}
}
int main()
{
citire();
prefix();
match();
freopen("strmatch.out","w",stdout);
printf("%d\n",nr);
for (i=1;i<=nr && i<=1000;++i)
printf("%d ",P[i]);
fclose(stdout);
return 0;
}