Pagini recente » Cod sursa (job #854006) | Cod sursa (job #1209314) | Cod sursa (job #654402) | Cod sursa (job #674342) | Cod sursa (job #160328)
Cod sursa(job #160328)
#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)
{
P[++nr]=i-L1+1;
if (nr==1000) return;
}
}
}
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;
}