Boyer Moore Algorithm for Pattern Searching (C++, java, python)

#include <bits/stdc++.h>
using namespace std;
# define NO_OF_CHARS 256 

void badCharHeuristic( string str, int size, int badchar[NO_OF_CHARS])
{
	int i;
	// Initializing all occurrences as -1
	for (i = 0; i < NO_OF_CHARS; i++)
		badchar[i] = -1;

	// Fill the actual value of last occurrence
	// of a character
	for (i = 0; i < size; i++)
		badchar[(int) str[i]] = i;
}

void search( string txt, string pat)
{
	int m = pat.size();
	int n = txt.size();
	int badchar[NO_OF_CHARS];

	/* Fill the bad character array by calling
	the preprocessing function badCharHeuristic()
	for given pattern */
	badCharHeuristic(pat, m, badchar);

	int s = 0; 
	while(s <= (n - m))
	{
		int j = m - 1;
        /* Keep reducing index j of pattern while
	characters of pattern and text are
	matching at this shift s */
		while(j >= 0 && pat[j] == txt[s + j])
			j--;

		/* If the pattern is present at current
		shift, then index j will become -1 after
		the above loop */
		if (j < 0)
		{
			cout << "pattern occurs at shift = " << s << endl;
			s += (s + m < n)? m-badchar[txt[s + m]] : 1;
		}
		else
			s += max(1, j - badchar[txt[s + j]]);
	}
}
/* Driver code */
int main()
{
	string txt= "ABAAABCD";
	string pat = "ABC";
	search(txt, pat);
	return 0;
}

NO_OF_CHARS = 256

def badCharHeuristic(string, size):
	# Initialize all occurrence as -1
	badChar = [-1]*NO_OF_CHARS

	# Fill the actual value of last occurrence
	for i in range(size):
		badChar[ord(string[i])] = i;

	# return initialized list
	return badChar

def search(txt, pat):
	m = len(pat)
	n = len(txt)

	# create the bad character list by calling
	# the preprocessing function badCharHeuristic()
	# for given pattern
	badChar = badCharHeuristic(pat, m)

	# s is shift of the pattern with respect to text
	s = 0
	while(s <= n-m):
		j = m-1

		# Keep reducing index j of pattern while
		# characters of pattern and text are matching
		# at this shift s
		while j>=0 and pat[j] == txt[s+j]:
			j -= 1

		# If the pattern is present at current shift,
		# then index j will become -1 after the above loop
		if j<0:
			print("Pattern occur at shift = {}".format(s))
			s += (m-badChar[ord(txt[s+m])] if s+melse 1)
		else:
			s += max(1, j-badChar[ord(txt[s+j])])


def main():
	txt = "ABAAABCD"
	pat = "ABC"
	search(txt, pat)

if __name__ == '__main__':
	main()

class Solution{
	
	static int NO_OF_CHARS = 256;

	static int max (int a, int b) { return (a > b)? a: b; }      //returns max of two numbers

	static void badCharHeuristic( char []str, int size,int badchar[])
	{

	// Initialize all occurrences as -1
	for (int i = 0; i < NO_OF_CHARS; i++)
		badchar[i] = -1;

	// Fill the actual value of last occurrence of a character
	for (int i = 0; i < size; i++)
		badchar[(int) str[i]] = i;
	}

	static void search( char txt[], char pat[])
	{
	int m = pat.length;
	int n = txt.length;

	int badchar[] = new int[NO_OF_CHARS];

	badCharHeuristic(pat, m, badchar);

	int s = 0; 
	while(s <= (n - m))
	{
		int j = m-1;

		/* Keep reducing index j of pattern while
			characters of pattern and text are
			matching at this shift s */
		while(j >= 0 && pat[j] == txt[s+j])
			j--;

		/* If the pattern is present at current
			shift, then index j will become -1 after
			the above loop */
		if (j < 0)
		{
			System.out.println("Patterns occur at shift = " + s);
			s += (s+m < n)? m-badchar[txt[s+m]] : 1;
		}
		else
			s += max(1, j - badchar[txt[s+j]]);
	}
}

	public static void main(String []args) {
		
		char txt[] = "ABAAABCD".toCharArray();
		char pat[] = "ABC".toCharArray();
		search(txt, pat);
	}
}

Pattern occurs at 4

/* C program for Boyer Moore Algorithm with
Good Suffix heuristic to find pattern in
given text string */

#include 
#include 

// preprocessing for strong good suffix rule
void preprocess_strong_suffix(int *shift, int *bpos,
								char *pat, int m)
{
	// m is the length of pattern
	int i=m, j=m+1;
	bpos[i]=j;

	while(i>0)
	{
		/*if character at position i-1 is not equivalent to
		character at j-1, then continue searching to right
		of the pattern for border */
		while(j<=m && pat[i-1] != pat[j-1])
		{
			/* the character preceding the occurrence of t in
			pattern P is different than the mismatching character in P,
			we stop skipping the occurrences and shift the pattern
			from i to j */
			if (shift[j]==0)
				shift[j] = j-i;

			//Update the position of next border
			j = bpos[j];
		}
		/* p[i-1] matched with p[j-1], border is found.
		store the beginning position of border */
		i--;j--;
		bpos[i] = j;
	}
}

//Preprocessing for case 2
void preprocess_case2(int *shift, int *bpos,
					char *pat, int m)
{
	int i, j;
	j = bpos[0];
	for(i=0; i<=m; i++)
	{
		/* set the border position of the first character of the pattern
		to all indices in array shift having shift[i] = 0 */
		if(shift[i]==0)
			shift[i] = j;

		/* suffix becomes shorter than bpos[0], use the position of
		next widest border as value of j */
		if (i==j)
			j = bpos[j];
	}
}

/*Search for a pattern in given text using
Boyer Moore algorithm with Good suffix rule */
void search(char *text, char *pat)
{
	// s is shift of the pattern with respect to text
	int s=0, j;
	int m = strlen(pat);
	int n = strlen(text);

	int bpos[m+1], shift[m+1];

	//initialize all occurrence of shift to 0
	for(int i=0;i<m+1;i++) shift[i]=0;

	//do preprocessing
	preprocess_strong_suffix(shift, bpos, pat, m);
	preprocess_case2(shift, bpos, pat, m);

	while(s <= n-m)
	{

		j = m-1;

		/* Keep reducing index j of pattern while characters of
			pattern and text are matching at this shift s*/
		while(j >= 0 && pat[j] == text[s+j])
			j--;

		/* If the pattern is present at the current shift, then index j
			will become -1 after the above loop */
		if (j<0)
		{
			printf("pattern occurs at shift = %d\n", s);
			s += shift[0];
		}
		else
			/*pat[i] != pat[s+j] so shift the pattern
			shift[j+1] times */
			s += shift[j+1];
	}

}

//Driver
int main()
{
	char text[] = "ABAAAABAACD";
	char pat[] = "ABA";
	search(text, pat);
	return 0;
}

# Python3 program for Boyer Moore Algorithm with
# Good Suffix heuristic to find pattern in
# given text string

# preprocessing for strong good suffix rule
def preprocess_strong_suffix(shift, bpos, pat, m):

	# m is the length of pattern
	i = m
	j = m + 1
	bpos[i] = j

	while i > 0:
		
		'''if character at position i-1 is
		not equivalent to character at j-1,
		then continue searching to right
		of the pattern for border '''
		while j <= m and pat[i - 1] != pat[j - 1]:
			
			''' the character preceding the occurrence
			of t in pattern P is different than the
			mismatching character in P, we stop skipping
			the occurrences and shift the pattern
			from i to j '''
			if shift[j] == 0:
				shift[j] = j - i

			# Update the position of next border
			j = bpos[j]
			
		''' p[i-1] matched with p[j-1], border is found.
		store the beginning position of border '''
		i -= 1
		j -= 1
		bpos[i] = j

# Preprocessing for case 2
def preprocess_case2(shift, bpos, pat, m):
	j = bpos[0]
	for i in range(m + 1):
		
		''' set the border position of the first character
		of the pattern to all indices in array shift
		having shift[i] = 0 '''
		if shift[i] == 0:
			shift[i] = j
			
		''' suffix becomes shorter than bpos[0],
		use the position of next widest border
		as value of j '''
		if i == j:
			j = bpos[j]

'''Search for a pattern in given text using
Boyer Moore algorithm with Good suffix rule '''
def search(text, pat):

	# s is shift of the pattern with respect to text
	s = 0
	m = len(pat)
	n = len(text)

	bpos = [0] * (m + 1)

	# initialize all occurrence of shift to 0
	shift = [0] * (m + 1)

	# do preprocessing
	preprocess_strong_suffix(shift, bpos, pat, m)
	preprocess_case2(shift, bpos, pat, m)

	while s <= n - m:
		j = m - 1
		
		''' Keep reducing index j of pattern while characters of
			pattern and text are matching at this shift s'''
		while j >= 0 and pat[j] == text[s + j]:
			j -= 1
			
		''' If the pattern is present at the current shift,
			then index j will become -1 after the above loop '''
		if j < 0:
			print("pattern occurs at shift = %d" % s)
			s += shift[0]
		else:
			
			'''pat[i] != pat[s+j] so shift the pattern
			shift[j+1] times '''
			s += shift[j + 1]

# Driver Code
if __name__ == "__main__":
	text = "ABAAAABAACD"
	pat = "ABA"
	search(text, pat)

/* Java program for Boyer Moore Algorithm with
Good Suffix heuristic to find pattern in
given text string */
class GFG
{

// preprocessing for strong good suffix rule
static void preprocess_strong_suffix(int []shift, int []bpos,
									char []pat, int m)
{
	// m is the length of pattern
	int i = m, j = m + 1;
	bpos[i] = j;

	while(i > 0)
	{
		/*if character at position i-1 is not
		equivalent to character at j-1, then
		continue searching to right of the
		pattern for border */
		while(j <= m && pat[i - 1] != pat[j - 1])
		{
			/* the character preceding the occurrence of t
			in pattern P is different than the mismatching
			character in P, we stop skipping the occurrences
			and shift the pattern from i to j */
			if (shift[j] == 0)
				shift[j] = j - i;

			//Update the position of next border
			j = bpos[j];
		}
		/* p[i-1] matched with p[j-1], border is found.
		store the beginning position of border */
		i--; j--;
		bpos[i] = j;
	}
}

//Preprocessing for case 2
static void preprocess_case2(int []shift, int []bpos,
							char []pat, int m)
{
	int i, j;
	j = bpos[0];
	for(i = 0; i <= m; i++)
	{
		/* set the border position of the first character
		of the pattern to all indices in array shift
		having shift[i] = 0 */
		if(shift[i] == 0)
			shift[i] = j;

		/* suffix becomes shorter than bpos[0],
		use the position of next widest border
		as value of j */
		if (i == j)
			j = bpos[j];
	}
}

/*Search for a pattern in given text using
Boyer Moore algorithm with Good suffix rule */
static void search(char []text, char []pat)
{
	// s is shift of the pattern
	// with respect to text
	int s = 0, j;
	int m = pat.length;
	int n = text.length;

	int []bpos = new int[m + 1];
	int []shift = new int[m + 1];

	//initialize all occurrence of shift to 0
	for(int i = 0; i < m + 1; i++)
		shift[i] = 0;

	//do preprocessing
	preprocess_strong_suffix(shift, bpos, pat, m);
	preprocess_case2(shift, bpos, pat, m);

	while(s <= n - m)
	{
		j = m - 1;

		/* Keep reducing index j of pattern while
		characters of pattern and text are matching
		at this shift s*/
		while(j >= 0 && pat[j] == text[s+j])
			j--;

		/* If the pattern is present at the current shift,
		then index j will become -1 after the above loop */
		if (j < 0)
		{
			System.out.printf("pattern occurs at shift = %d\n", s);
			s += shift[0];
		}
		else
		
			/*pat[i] != pat[s+j] so shift the pattern
			shift[j+1] times */
			s += shift[j + 1];
	}

}

// Driver Code
public static void main(String[] args)
{
	char []text = "ABAAAABAACD".toCharArray();
	char []pat = "ABA".toCharArray();
	search(text, pat);
}
}

pattern occurs at shift = 0
pattern occurs at shift = 5