Pagini recente » Cod sursa (job #3280823) | Cod sursa (job #768311) | Cod sursa (job #760986) | Cod sursa (job #2616903) | Cod sursa (job #2808012)
#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 za[LMAX + 5], zb[LMAX + 5];
vector<int> matches;
void calc_za() {
za[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]
za[i] = min(za[i - l], r - i + 1);
/// adaug cat de multe caractere pot la prefixul curent
while(i + za[i] < la && a[i + za[i]] == a[za[i]])
za[i]++;
/// actualizez [l, r] astfel incat r sa fie maxim
if(i + za[i] - 1 > r)
l = i, r = i + za[i] - 1;
}
}
void calc_zb() {
for(int i = 0, l = 0, r = -1; i < lb; i++) {
if(i <= r)
zb[i] = min(za[i - l], r - i + 1);
while(i + zb[i] < lb && zb[i] < la && a[zb[i]] == b[i + zb[i]])
zb[i]++;
if(i + zb[i] - 1 > r)
l = i, r = i + zb[i] - 1;
if(zb[i] == la)
matches.push_back(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_za();
calc_zb();
printf("%d\n", matches.size());
for(int x: matches)
printf("%d ", x);
return 0;
}