Pagini recente » Cod sursa (job #2809844) | Cod sursa (job #987256) | Cod sursa (job #2391512) | Cod sursa (job #1402619) | Cod sursa (job #786427)
Cod sursa(job #786427)
#include <stdio.h>
#include <string.h>
#define base 67
#define MAX_N 2000010
const int prim[2] = {10007, 31307};
int n, m;
int pown[2];
int ans[MAX_N];
char A[MAX_N], B[MAX_N];
inline int get_number(char c) {
if ('0' <= c && c <= '9')
return c - '0' + 1;
if ('a' <= c && c <= 'z')
return c - 'a' + 11;
return c - 'A' + 37;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", A);
scanf("%s", B);
n = strlen(A);
m = strlen(B);
pown[0] = pown[1] = 1;
for (int i = 1; i < n; i++)
for (int j = 0; j < 2; j++)
pown[j] = (pown[j] * base) % prim[j];
int CA[2] = {0, 0};
for (int i = 0; i < n; i++)
for (int j = 0; j < 2; j++)
CA[j] = (CA[j] * base + get_number(A[i])) % prim[j];
int CB[2] = {0, 0};
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
if (i >= n) {
CB[j] = CB[j] - get_number(B[i - n]) * pown[j];
CB[j] = CB[j] % prim[j];
if (CB[j] < 0)
CB[j] += prim[j];
}
CB[j] = (CB[j] * base + get_number(B[i])) % prim[j];
}
if (i >= n && CA[0] == CB[0] && CA[1] == CB[1])
ans[++ans[0]] = i;
}
printf("%d\n", ans[0]);
ans[0] = ans[0] < 1000 ? ans[0] : 1000;
for (int i = 1; i <= ans[0]; i++)
printf("%d ", ans[i] - n + 1);
printf("\n");
return 0;
}