Pagini recente » Cod sursa (job #3359816) | Cod sursa (job #3359168) | Cod sursa (job #3359274) | Cod sursa (job #3359162) | Cod sursa (job #3359166)
#include <cstdio>
#include <cstring>
#include <ios>
#include<vector>
#include<algorithm>
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;
vector<int> solutions;
for (int i = m + 1; i < n; i++) {
if (z[i] >= m)
solutions.push_back(i - m - 1);
}
printf("%d\n", solutions.size());
int to_print = min((int)solutions.size(), 1000);
for (int i = 0; i < to_print; i++)
printf("%d ", solutions[i]);
return 0;
}