// Algorytm Boyer-Moore
// Tomasz Lubinski (c) 2007
// www.algorytm.org

#include "stdio.h"

//size of the alphabet
#define ASIZE 255

//max. size of the pattern
#define PSIZE 100

//max. size of the text
#define TSIZE 1000

#define MAX(a, b) (a > b) ? a : b

int bad_character_shift[ASIZE];
int good_suffix_shift[PSIZE];
int suff[PSIZE];

//prepare bad character shift table
void pre_bad_character_shift(char *pattern)
{
   int i;
   int m = strlen(pattern);

   for (i = 0; i < ASIZE; i++)
   {
      bad_character_shift[i] = m;
   }

   for (i = 0; i < m - 1; ++i)
   {
      bad_character_shift[pattern[i]] = m - i - 1;
   }
}

//prepare suff table
void pre_suff(char *pattern)
{
   int i, j;
   int m = strlen(pattern);

   suff[m - 1] = m;
   for (i = m - 2; i >= 0; --i) {
      for (j = 0; j <= i && pattern[i-j] == pattern[m-j-1]; j++);
      suff[i] = j;
   }

}

//prepare good_suffix_shift table
void pre_good_suffix_shift(char *pattern)
{
   int i,j;
   int m = strlen(pattern);

   pre_suff(pattern);

   for (i = 0; i < m; i++)
   {
      good_suffix_shift[i] = m;
   }

   j = 0;
   for (i = m - 1; i >= 0; --i)
   {
      if (suff[i] == i + 1)
      {
         for (; j < m - 1 - i; ++j)
         {
            good_suffix_shift[j] = m - 1 - i;
         }
      }
   }

   for (i = 0; i <= m - 2; ++i)
   {
      good_suffix_shift[m - 1 - suff[i]] = m - 1 - i;
   }
}

//Boyer-Moore algorithm
void BM(char *text, char *pattern)
{
   int i, j;
   int m = strlen(pattern);
   int n = strlen(text);

   pre_bad_character_shift(pattern);
   pre_good_suffix_shift(pattern);

   j = 0;
   while (j <= n - m) {
      for (i = m - 1; i >= 0 && pattern[i] == text[i + j]; --i);
      if (i < 0) {
         printf("%d ", j);
         j += good_suffix_shift[0];
      }
      else
         j += MAX(good_suffix_shift[i], bad_character_shift[text[i + j]] - m + 1 + i);
   }
}

//Get data
int main()
{
   char pattern[PSIZE];
   char text[TSIZE];

   printf("Podaj tekst\n");
   scanf("%s", text);

   printf("Podaj wzorzec\n");
   scanf("%s", pattern);

   BM(text, pattern);
}