Pagini recente » Cod sursa (job #2122079) | Cod sursa (job #2415990) | Cod sursa (job #1161750) | Cod sursa (job #387852) | Cod sursa (job #2808031)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int LMAX = 2000000;
int la, lb;
char a[LMAX + 5], b[LMAX + 5];
int z[LMAX + 5];
int nr_matches;
int matches[LMAX + 5];
void calc_z() {
z[0] = 0;
for(int i = 1, l = 0, r = 0; i < la; i++) {
if(i <= r) /// ma aflu in interiorul prefixului deja calculat, [l, r]
z[i] = min(z[i - l], r - i + 1);
/// adaug cat de multe caractere pot la prefixul curent
while(i + z[i] < la && a[i + z[i]] == a[z[i]])
z[i]++;
/// actualizez [l, r] astfel incat r sa fie maxim
if(i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
}
void calc_matches() {
for(int i = 0, l = 0, r = 0; i < lb; i++) {
int crt = 0;
if(i <= r)
crt = min(z[i - l], r - i + 1);
while(i + crt < lb && crt < la && a[crt] == b[i + crt])
crt++;
if(i + crt - 1 > r)
l = i, r = i + crt - 1;
if(crt == la)
matches[++nr_matches] = i;
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", a, b);
la = strlen(a);
lb = strlen(b);
calc_z();
calc_matches();
printf("%d\n", nr_matches);
for(int i = 1; i <= nr_matches; i++)
printf("%d ", matches[i]);
return 0;
}