Pagini recente » Cod sursa (job #1737137) | Cod sursa (job #1709853) | Cod sursa (job #165670) | Cod sursa (job #1728809) | Cod sursa (job #166944)
Cod sursa(job #166944)
#include <stdio.h>
#include <cstring>
#define maxim 20010
long n,m,i,k,nr;
long p[maxim+2],sol[maxim+2];
char a[maxim+2],b[maxim+2];
void pi()
{
k=0;
for (i=2; i<=n; i++)
{
while (k && a[i]!=a[k+1])
k=p[k];
if (a[k+1]==a[i]) { k++; }
p[i]=k;
}
}
void kmp()
{
n=strlen(a+1)-1;
m=strlen(b+1)-1;
pi(); nr=0; k=0; i=0;
for (i=1; i<=m; i++)
{
while (k && b[i]!=a[k+1])
k=p[k];
if (b[i]==a[k+1]) {k++;}
if (k==n) { nr++; sol[nr]=i-n; k=p[k]; }
}
}
int main(void)
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(a+1, maxim, stdin);
fgets(b+1, maxim, stdin);
kmp();
printf("%ld\n", nr);
if (nr>1000) { nr=1000; }
for (i=1; i<=nr ;i++) { printf("%ld ", sol[i]); }
fclose(stdin); fclose(stdout);
return 0;
}