Pagini recente » Cod sursa (job #2742216) | Cod sursa (job #1255764) | Cod sursa (job #1764580) | Cod sursa (job #1088812) | Cod sursa (job #1457664)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXL 2000000
int w_len, s_len, last, t[MAXL], n[1000], N;
char w[MAXL], s[MAXL];
int main()
{
int i, j;
// open files
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
// read strings
scanf("%[^\n]", w); getchar();
scanf("%[^\n]", s); getchar();
w_len = strlen(w);
s_len = strlen(s);
// bake partial match table
t[0] = -1;
i = 2;
while (i < w_len)
{
if (w[i - 1] == w[last])
{
last++;
t[i] = last;
i++;
}
else if (last > 0)
{
last = t[last];
}
else
{
t[i] = 0;
i++;
}
}
/*
for (i = 0; i < w_len; i++)
{
printf("%d", t[i]);
}
*/
// search for matches
i = 0;
j = 0;
while (i + j < s_len)
{
if (w[j] == s[i + j])
{
if (j == w_len - 1)
{
if (N < 1000) n[N] = i;
N++;
}
j++;
}
else
{
if (t[j] > -1)
{
i += j - t[j];
j = t[j];
}
else
{
j = 0;
i++;
}
}
}
// print results
printf("%d\n", N);
for (i = 0; i < N; i++)
{
printf("%d ", n[i]);
}
return 0;
}