Pagini recente » Cod sursa (job #517342) | Cod sursa (job #65104) | Cod sursa (job #526682) | Cod sursa (job #964490) | Cod sursa (job #1095135)
#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;
if (sol <= 1000)
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;
}