Pagini recente » Cod sursa (job #2914552) | Cod sursa (job #2662840) | Cod sursa (job #1882790) | Cod sursa (job #1161540) | Cod sursa (job #1446429)
#include <stdio.h>
#include <math.h>
#include <string.h>
#define NMAX 2000002
#define MMAX 1000
#define MOD 104729
static int match[MMAX];
static char Text[NMAX], Pattern[NMAX];
static size_t read(char *s, int lim)
{
char *p;
fgets(s, lim, stdin);
if ((p = strchr(s, '\n')))
*p = '\0';
return strlen(s);
}
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 * 26 + s[i]) % MOD;
return hh;
}
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);
plen = read(Pattern, sizeof Pattern);
tlen = read(Text, sizeof Text);
h = (unsigned long long) pow(26, plen - 1) % MOD;
ph = hash(Pattern, plen);
th = hash(Text, plen);
if (ph == th && !strncmp(Pattern, Text, plen))
match[N++] = 0;
for (i = 1; i <= tlen - plen; i++) {
th = (26 * (th - Text[i - 1] * h) + 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;
}