Pagini recente » Cod sursa (job #1522705) | Cod sursa (job #112399) | Cod sursa (job #2499537) | Cod sursa (job #842235) | Cod sursa (job #2791133)
#include <cstdio>
#include <cstring>
#define NMAX 2000005
char a[NMAX], b[NMAX];
int nrla, nrlb, p[NMAX], nrrez, pozrez[1005];
void citire() {
scanf("%s", &a);
scanf("%s", &b);
nrla = strlen(a);
nrlb = strlen(b);
}
void formare_prefixe() {
p[0] = -1;
for (int i = 0, j = -1; i < nrla; ++i) {
while (j >= 0 && a[i] != a[j])
j = p[j];
j++;
p[i + 1] = j;
}
}
void kmp() {
int j = 0;
for (int i = 0; i < nrlb; ++i) {
while (j >= 0 && b[i] != a[j])
j = p[j];
j++;
if (j == nrla) {
j = p[j];
nrrez++;
if (nrrez <= 1000)
pozrez[nrrez] = i - nrla + 1;
}
}
}
void afisare() {
printf("%d\n", nrrez);
int limita = (nrrez < 1000) ? nrrez : 1000;
for (int i = 1; i <= limita; ++i)
printf("%d ", pozrez[i]);
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
formare_prefixe();
kmp();
afisare();
return 0;
}