Pagini recente » Cod sursa (job #2929250) | Cod sursa (job #1459522) | td1 | Cod sursa (job #219479) | Cod sursa (job #2062978)
#include <stdio.h>
#include <string.h>
#define minim(a, b) ((a < b) ? a : b)
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100009
char a[MAXN], b[MAXN];
char match[MAXN];
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s", a, b);
int n = strlen(a);
int m = strlen(b);
int hashA1=0, hashA2=0, hash1=0, hash2=0, P1 = 1, P2 = 1, nr = 0;
if (n > m) {
printf("0\n");
return 0;
}
for (int i = 0; i< n; ++i) {
hashA1 = (hashA1 * P + a[i]) % MOD1;
hashA2 = (hashA2 * P + a[i]) % MOD2;
hash1 = (hash1 * P + b[i]) % MOD1;
hash2 = (hash2 * P + b[i]) % MOD2;
if (i != 0) {
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
}
if (hash1 == hashA1 && hash2 == hashA2) {
match[0] = 1; ++nr;
}
for (int i = n; i < m; ++i) {
hash1 = ((hash1 + MOD1 - (b[i-n] * P1) % MOD1) * P + b[i]) % MOD1;
hash2 = ((hash2 + MOD2 - (b[i-n] * P2) % MOD2) * P + b[i]) % MOD2;
if (hash1 == hashA1 && hash2 == hashA2) {
match[i-n+1] = 1; ++nr;
}
}
printf("%d\n", nr);
for (int i = 0; i <= minim(m, 1000); ++i)
if (match[i])
printf("%d ", i);
printf("\n");
return 0;
}