Pagini recente » Cod sursa (job #246427) | Cod sursa (job #2339917) | Cod sursa (job #48207) | Cod sursa (job #2738289) | Cod sursa (job #1446508)
#include <stdio.h>
#include <string.h>
#define NMAX 2000005
#define MMAX 1000
#define MOD 100007
static int match[NMAX];
static char Text[NMAX], Pattern[NMAX];
static unsigned long long hash(char *s, size_t len)
{
unsigned long long hh = 0;
unsigned long i;
for (i = 0; i < len; i++)
hh = (hh * 62 + s[i]) % MOD;
return hh;
}
static unsigned long long pw(int base, int p)
{
unsigned long long aux;
if (p == 0)
return 1;
if (p == 1)
return base % MOD;
aux = pw(base, p >> 1) % MOD;
if (p & 1)
return (((aux * aux) % MOD) * base % MOD) % MOD;
else
return aux * aux % MOD;
}
int main(void)
{
char *t = Text;
unsigned long long ph, th, h;
size_t tlen, plen, i;
int N = 0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", Pattern, Text);
plen = strlen(Pattern);
tlen = strlen(Text);
h = (unsigned long long) pw(62, plen - 1) % MOD;
ph = hash(Pattern, plen);
th = hash(Text, plen);
if (ph == th && !memcmp(Pattern, Text, plen))
match[N++] = 0;
for (i = 1; i <= tlen - plen; i++) {
th = (62 * (th - Text[i - 1] * h % MOD + MOD) + Text[i + plen - 1]) % MOD;
if (th == ph && !strncmp(t + i, Pattern, plen))
match[N++] = i;
}
printf("%d\n", N);
for (i = 0; i < N && i < MMAX; i++)
printf("%d ", match[i]);
printf("\n");
return 0;
}