Pagini recente » Cod sursa (job #1446812) | Cod sursa (job #740628) | Cod sursa (job #1593051) | Cod sursa (job #94098) | Cod sursa (job #1414784)
#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_N = 2000005;
int N, M, ans;
int z[2 * MAX_N], sol[1002];
char A[2 * MAX_N], B[MAX_N];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
A[0] = B[0] = ' ';
fgets(A + 1, MAX_N - 2, stdin);
fgets(B + 1, MAX_N - 2, stdin);
N = strlen(A) - 2;
M = strlen(B) - 2;
int L = N;
A[++L] = '#';
for(int i = 1; i <= M; ++i) {
A[++L] = B[i];
}
for(int i = 2, C = 0, R = 0; i <= L; ++i) {
if(R >= i) {
z[i] = min(z[i - C + 1], R - i + 1);
}
while(i + z[i] <= L && A[i + z[i]] == A[z[i] + 1]) {
++z[i];
}
}
for(int i = N + 2; i <= L; ++i) {
if(z[i] == N) {
++ans;
if(ans <= 1000) {
sol[ans] = i - N - 2;
}
}
}
printf("%d\n", ans);
for(int i = 1; i <= min(ans, 1000); ++i) {
printf("%d ", sol[i]);
}
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}