Pagini recente » Cod sursa (job #1447800) | Cod sursa (job #3169945) | Cod sursa (job #2598675) | Cod sursa (job #2604045) | Cod sursa (job #1448149)
#include <stdio.h>
#include <string.h>
#define NMAX 2000005
#define MMAX 1000
static int BC['z' + 1][NMAX] = {-1}, match[MMAX];
static char Pattern[NMAX], Text[NMAX];
static void print(int n)
{
int i;
printf("%d\n", n);
for (i = 0; i < n && i < MMAX; i++)
printf("%d ", match[i]);
printf("\n");
}
static void bad_char(size_t plen)
{
int i, j;
for (i = 1; i < plen; i++) {
for (j = 0; j <= 'z'; j++)
BC[j][i] = BC[j][i - 1];
BC[Pattern[i - 1]][i] = i - 1;
}
}
static int boyer_moore(size_t tlen, size_t plen)
{
int i, j, k, n = 0;
bad_char(plen);
for (i = plen - 1; i < tlen; ) {
j = plen - 1;
k = i;
while (j >= 0 && Pattern[j] == Text[k]) {
j--;
k--;
}
if (j == -1) {
if (n < MMAX)
match[n] = k + 1;
n++;
i++;
} else {
i += j - BC[Text[k]][j];
}
}
return n;
}
int main(void)
{
size_t tlen, plen;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", Pattern, Text);
plen = strlen(Pattern);
tlen = strlen(Text);
print(boyer_moore(tlen, plen));
return 0;
}