Pagini recente » Cod sursa (job #1299952) | Cod sursa (job #2896722) | Cod sursa (job #2699005) | Cod sursa (job #2091725) | Cod sursa (job #786399)
Cod sursa(job #786399)
#include <stdio.h>
#include <string.h>
#define base 67
#define MAX_N 2000010
int n, m;
int ans[MAX_N];
char A[MAX_N], B[MAX_N];
inline unsigned 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);
unsigned int pown = 1;
for (int i = 1; i < n; i++)
pown = pown * base;
unsigned int CA = 0;;
for (int i = 0; i < n; i++)
CA = CA * base + get_number(A[i]);
unsigned int CB = 0;
for (int i = 0; i < m; i++) {
if (i >= n)
CB = CB - get_number(B[i - n]) * pown;
CB = CB * base + get_number(B[i]);
if (i >= n && CA == CB)
ans[++ans[0]] = i;
}
printf("%d\n", ans[0]);
for (int i = 1; i <= ans[0]; i++)
printf("%d ", ans[i] - n + 1);
printf("\n");
return 0;
}