Pagini recente » Cod sursa (job #1296421) | cheerleader | Profil StarGold2 | Cod sursa (job #2409056) | Cod sursa (job #787556)
Cod sursa(job #787556)
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#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);
int pown = 1;
for (int i = 1; i < n; i++)
pown = pown * base;
int CA = 0;;
for (int i = 0; i < n; i++)
CA = CA * base + get_number(A[i]);
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 - 1 && CA == CB)
ans[++ans[0]] = i;
}
printf("%d\n", ans[0]); ans[0] = min(ans[0], 1000);
for (int i = 1; i <= ans[0]; i++)
printf("%d ", ans[i] - n + 1);
printf("\n");
return 0;
}