Pagini recente » Cod sursa (job #1032695) | Cod sursa (job #3223879) | Cod sursa (job #1917153) | Cod sursa (job #543982) | Cod sursa (job #1727025)
#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <math.h>
#define NMAX 2000005
char str_a[NMAX], str_b[NMAX];
int ans[NMAX];
const int M = 3666013;
int k_to_the_n;
int _min (int a, int b) {
return a < b ? a : b;
}
long long compute_hash (char pattern[], int length) {
int i;
int q = 0x100;
long long k = 1;
long long hash = 0;
for (i = 0; i < length; ++i) {
hash = (hash + pattern[length - i - 1] * k) % M;
k_to_the_n = k;
k = k * q % M;
}
return hash;
}
int _str_cmp (char str1[], char str2[], int length) {
int i;
for (i = 0; i < length; ++i) {
if (str1[i] != str2[i])
return 0;
}
return 1;
}
int main () {
int i, ans_ind = 0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf ("%s", str_a);
scanf ("%s", str_b);
int len_a = strlen(str_a),
len_b = strlen(str_b);
long long hash_for_a = compute_hash(str_a, len_a);
long long init_hash = compute_hash(str_b, len_a);
if (init_hash == hash_for_a && _str_cmp(str_a, str_b, len_a)) {
ans[ans_ind++] = 0;
}
for (i = len_a; i < len_b; ++i) {
init_hash -= str_b[i - len_a] * k_to_the_n;
while (init_hash < 0) init_hash += M;
init_hash = init_hash * 0x100 % M;
init_hash = (init_hash + str_b[i]) % M;
if (init_hash == hash_for_a && _str_cmp(str_a, str_b + i - len_a + 1, len_a)) {
ans[ans_ind++] = i - len_a + 1;
}
}
int k = _min (ans_ind, 1000);
printf ("%d\n", ans_ind);
for (i = 0; i < k; ++i) {
printf ("%d ", ans[i]);
}
}