Pagini recente » Cod sursa (job #3359718) | Cod sursa (job #3359716) | Cod sursa (job #3359723) | Cod sursa (job #3359722) | Cod sursa (job #3359165)
#include <cstdio>
#include <cstring>
#include <ios>
using namespace std;
const int NMAX = 2e6 + 10;
const char DELIMITATOR = '#';
void compute_strings_z(char a[], char b[]) {
strcat(a, "#");
strcat(a, b);
}
void compute_z(char a[], int z[]) {
int l, r;
int n = strlen(a);
l = r = 0;
z[0] = 0;
for (int i = 1; i < n; i++) {
if (l <= i && i <= r) z[i] = z[i - l];
else z[i] = 0;
while ((i + z[i]) < n && a[z[i]] == a[i + z[i]]) z[i]++;
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
}
char a[NMAX], b[NMAX];
int z[NMAX]; // z[i] = cel mai lung prefix comun intre sufixul de la pozitia 0 si sufixul la pozitia i
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", &a);
scanf("%s", &b);
compute_strings_z(a, b);
compute_z(a, z);
int n = strlen(a);
int m = n - strlen(b) - 1;
int cnt = 0;
for (int i = m + 1; i < n; i++) {
if (z[i] >= m)
cnt++;
}
printf("%d\n", cnt);
for (int i = m + 1; i < n && cnt > 0; i++) {
if (z[i] >= m) {
printf("%d ", i - m - 1);
cnt--;
}
}
return 0;
}