Pagini recente » Cod sursa (job #3266033) | Cod sursa (job #1169934) | Cod sursa (job #2228108) | Cod sursa (job #1202613) | Cod sursa (job #160318)
Cod sursa(job #160318)
#include <stdio.h>
#include <string.h>
#define Lmax 2000002
char A[Lmax],B[Lmax],i;
int L1,L2;
int T[Lmax],P[Lmax],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) 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)
printf("%d ",P[i]);
fclose(stdout);
return 0;
}