#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BOYER_MOORE
#define KNUTH_MORRIS_PRATT
#define max(a,b) ((a>b) ? a : b)


int main(int argc, char ** argv)
{
	int q, l, i, r, j;
	char * P = argv[1];
	char T [1000];	
	fgets (T, 999, stdin);
	int M = strlen(P)-1; // length of pattern
	int N = strlen(T)-2; // length of text
	char * next = malloc (M+1);
	char * txen = malloc (M+1);
	char * P_ = malloc (M+1);
	char * suffix = malloc (M+1);
	char last [256];
	

#ifdef BOYER_MOORE
	// InitLast(P);
	for (i=0; i< 256; i++)
	{
		last[i] = 0;
	}
	for (j=1; j<=M; j++)
	{
		last [P[j]] = j;
		printf ("last[%c] = %d\n", P[j], j);
	}
	// InitSuffix(P);
	next[1] = 0;
	l=0;
	for (q=2; q<=M; q++)
	{
		while ((l>0) && (P[l+1] != P[q])) l= next[l];
		if (P[l+1] == P[q]) l++;
		next[q] = l;
		printf ("next[%d] = %d\n", q, l);
	}
	printf ("verkehrtes P: ");
	for (i=1; i<=M; i++)
	{
		P_[i] = P[M-i+1];
		printf ("%c", P[M-i+1]);
	} printf ("\n");
	txen[1] = 0;
	l=0;
	for (q=2; q<=M; q++)
	{
		while ((l>0) && (P_[l+1] != P_[q])) l= txen[l];
		if (P_[l+1] == P_[q]) l++;
		txen[q] = l;
		printf ("txen[%d] = %d\n", q, l);
	}
	for (j=0; j<=M; j++)
	{
		suffix[j] = M-next[M];
		printf ("suffix[%d] = %d\n", j, M-next[M]);
	}
	for (q=1; q<=M; q++)
	{
		j = M - txen[q];
		if (suffix[j] > q-txen[q])
		{
			suffix[j] = q - txen[q];
			printf ("suffix[%d] = %d (q=%d)\n", j, q - txen[q], q);
		}	
	}

	//Boyer Moore
	i=0;
	while (i<=N-M)
	{
		j=M;
		printf ("letter %c pattern %c\n", T[i+j], P[j]);
		while ((j>0) && (P[j] == T[i+j])) j--;
		if (j==0)
		{
			printf ("found at %d\n", i+1-M);
			i = i + suffix[M-1];
		} else {
			i = i + max(suffix[j], j-last[T[i+j]]);
		}
	}
#else
#ifdef KNUTH_MORRIS_PRATT
	next[1] = 0;
	l=0;
	for (q=2; q<=M; q++)
	{
		while ((l>0) && (P[l+1] != P[q])) l= next[l];
		if (P[l+1] == P[q]) l++;
		next[q] = l;
		printf ("next[%d] = %d\n", q, l);
	}

	j=0;
	for (i=1; i<=N; i++)
	{
		printf ("letter %c, pattern %c\n", T[i], P[j+1]);
		while ((j>0) && (P[j+1] != T[i]))
		{
			printf ("letter %c, pattern %c not found - i: %d, j: %d, go to %d\n", T[i],  P[j+1],  i, j, next[j]);
			j= next[j];
		}
		if (P[j+1] == T[i]) j++;
		if (j==M)
		{
			printf ("found at %d\n", i+1-M);
			j = next[j];
		}
	}
#else
	for (i=0; i<= N-M; i++)
	{
		j=1;
		while ((j<=M) && (P[j] == T[i+j]))
		{
			printf ("cmp P[j]: %c,  T[i+j]: %c, i: %d, j: %d\n", P[j], T[i+j], i, j);
			j++;
		}
		if (j==M+1) printf ("found at %d\n", i+1);
	}
#endif
#endif
}