#!/usr/bin/env python
#Author: Shriphani Palakodety
#Mail: shriphani@shriphani.com
#Mail2: spalakod@purdue.edu
#blog: http://shriphani.com/blog

bcs = {} #the table

def goodSuffixShift(key):

	for i in xrange(len(key)-1, -1, -1):
		if key[i] not in bcs.keys():
			bcs[key[i]] = len(key)-i-1



def search(text, key):
	
	i = len(key)-1

	index = len(key) -1

	j = i

	while True:


		if i == 0:
			return j

		elif j > len(text):
			return "not found"


		elif text[j] != key[i] and text[j] not in bcs.keys():
			j += len(key)
			i = index

		elif text[j] != key[i] and text[j] in bcs.keys():
			j += bcs[text[j]]
			i = index

		else:
			j -= 1
			i -= 1


			
	

key_list = ["POWER", "HOUSE", "COMP", "SCIENCE", "SHRIPHANI", "BRUAH"]

text = "SHRIPHANI IS A COMPUTER SCIENCE POWERHOUSE"

for key in key_list:
	goodSuffixShift(key)
	print key + " location: " + str(search(text, key))
	bcs = {}