Pagini recente » Cod sursa (job #1041018) | Cod sursa (job #971071) | Cod sursa (job #1639387) | Cod sursa (job #2855852) | Cod sursa (job #172004)
Cod sursa(job #172004)
#include <stdio.h>
#include <string.h>
#define maxN 2000005
char a[maxN], b[maxN];
int p[maxN];
int na, nb;
void calcul_prefix()
{
int k, i;
k = 0;
p[1] = 0;
for(i=2; i<=na; ++i)
{
while(k>0 && (a[k+1] != a[i]))
k = p[k];
if(a[k+1]==a[i]) k++;
p[i]=k;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n", a + 1);
scanf("%s\n", b + 1);
fclose(stdin);
na = strlen(a+1);
nb = strlen(b+1);
calcul_prefix();
int idx[maxN], q=0, cnt=0, i;
for(i=1;i<=nb;++i)
{
while((q>0) && (a[q+1] != b[i]))
q=p[q];
if(a[q+1]==b[i])
q++;
if(q==na)
{
idx[++cnt] = nb-i+1;
}
}
printf("%d\n",cnt);
if(cnt>1000) cnt=1000;
for(i=1;i<=cnt;++i) printf("%d ", idx[i]);
printf("\n");
fclose(stdout);
return 0;
}