Pagini recente » Cod sursa (job #1683548) | Cod sursa (job #506724) | Cod sursa (job #2391346) | Cod sursa (job #1812569) | Cod sursa (job #172022)
Cod sursa(job #172022)
#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);
//printf("am deschis fisieru\'\n");
scanf("%s\n", a + 1);
scanf("%s\n", b + 1);
//printf("am citit %s, %s\n",a+1,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] = i-na+1;
}
}
printf("%d\n",cnt);
if(cnt>1000) cnt=1000;
for(i=1;i<=cnt;++i) printf("%d ", idx[i]-1);
printf("\n");
fclose(stdout);
return 0;
}