Pagini recente » Cod sursa (job #1655543) | Cod sursa (job #1690546) | Cod sursa (job #1254958) | Cod sursa (job #2084585) | Cod sursa (job #631164)
Cod sursa(job #631164)
#include <stdio.h>
#include <string.h>
#define MAXN 2000001
#define P 73
char a[MAXN], b[MAXN];
int n, m;
int hash11, hash12, P1, P2;
char match[MAXN];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", a, b);
n = strlen(a);
m = strlen(b);
P1 = P2 = 1;
hash11 = hash12 = 0;
for (int i = 0; i < n; i++)
{
hash11 = (hash11 * P + a[i]) % 100007;
hash12 = (hash12 * P + a[i]) % 100021;
if (i != 0)
P1 = (P1 * P) % 100007,
P2 = (P2 * P) % 100021;
}
if (n > m)
{
printf("0\n");
return 0;
}
int hash21 = 0, hash22 = 0;
for (int i = 0; i < n; i++)
hash21 = (hash21 * P + b[i]) % 100007,
hash22 = (hash22 * P + b[i]) % 100021;
int nr = 0;
if (hash21 == hash11 && hash22 == hash12)
match[0] = 1, nr++;
for (int i = n; i < m; i++)
{
hash21 = ((hash21 - (b[i - n] * P1) % 100007 + 100007) * P + b[i]) % 100007;
hash22 = ((hash22 - (b[i - n] * P2) % 100021 + 100021) * P + b[i]) % 100021;
if (hash21 == hash11 && hash22 == hash12)
match[ i - n + 1 ] = 1, nr++;
}
printf("%d\n", nr);
nr = 0;
for (int i = 0; i < m && nr < 1000; i++)
if (match[i])
nr++,
printf("%d ", i);
printf("\n");
return 0;
}