Pagini recente » Cod sursa (job #602095) | Cod sursa (job #1786718) | Cod sursa (job #1037149) | Cod sursa (job #1243618) | Cod sursa (job #200081)
Cod sursa(job #200081)
#include <stdio.h>
#include <string.h>
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define NMAX 2000001
int n,m,i,k,nr;
int V[NMAX];
int pi[NMAX];
char A[NMAX],B[NMAX];
void read()
{
freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);
scanf("%s\n", A+1);
scanf("%s\n", B+1);
n=strlen(A+1);
m=strlen(B+1);
}
void prefix()
{
pi[1]=0;
k=0;
for (i=2;i<=n;++i) {
while (k>0 && A[i]!=A[k+1]) k=pi[k];
if (A[i]==A[k+1]) ++k;
pi[i]=k;
}
}
void KMP()
{
k=0;
for (i=1; i<=m; ++i) {
while (A[k+1]!=B[i]&&k>0) k=pi[k];
if (A[k+1]==B[i])
++k;
if (k==n) {
++nr;
if (nr<1000)
V[nr]=i-n;
}
}
}
void print()
{
printf("%d\n",nr);
for (i=1;i<=nr && i<=1000;i++)
printf("%d ",V[i]);
}
int main()
{
read();
prefix();
KMP();
print();
return 0;
}