Pagini recente » Cod sursa (job #727992) | Cod sursa (job #559791) | Cod sursa (job #2873361) | Cod sursa (job #232678) | Cod sursa (job #1095128)
#include <stdio.h>
#include <string.h>
#define Nmax 2000005
char a[Nmax], b[Nmax];
int n, m, sol, c;
int pi[Nmax], where[Nmax];
void read()
{
freopen("strmatch.in", "r", stdin);
scanf("%s", a + 1);
scanf("%s", b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
fclose(stdin);
}
void kmp()
{
int k;
k = 0;
for (int i = 2; i <= n; ++i){
while (k > 0 && a[k + 1] != a[i])
k = pi[k];
if (a[k + 1] == a[i])
++k;
pi[i] = k;
}
k = 0;
for (int i = 1; i <= m; ++i){
while (k > 0 && a[k + 1] != b[i])
k = pi[k];
if (a[k + 1] == b[i])
++k;
if (k == n && sol < 1000) {
++sol;
where[c++] = i - n;
}
}
}
void write()
{
freopen("strmatch.out", "w", stdout);
printf("%d\n", sol);
for (int i = 0; i < c; ++i)
printf("%d ", where[i]);
}
int main()
{
read();
kmp();
write();
return 0;
}