search-engine

Let us see how search engines work. Consider the following simple auto complete feature. When you type some characters in the text bar, the engine automatically gives best matching options among it's database. Your job is simple. Given an incomplete search text, output the best search result.

Each entry in engine's database has a priority factor attached to it. We consider a result / search suggestion best if it has maximum weight and completes the given incomplete search query. For each query in the input, print the maximum weight of the string in the database, that completes the given incomplete search string. In case no such string exists, print -1.

INPUT

First line contains two integers n and q, which represent number of database entries and number of search queries need to be completed. Next n lines contain a string s and an integer weight, which are the database entry and it's corresponding priority.

Next q lines follow, each line having a string t, which needs to be completed.

OUTPUT

Output q lines, each line containing the maximum possible weight of the match for given query, else -1, in case no valid result is obtained.

CONSTRAINTS

1 ≤ n, weight, len(s), len(t) ≤ 10^6
1 ≤ q ≤ 10^5
total length of all strings in database entries ≤ 10^6
total length of all query strings ≤ 10^6

SAMPLE INPUT
2 1
hackerearth 10
hackerrank 9
hacker

SAMPLE OUTPUT
10

Source: hackerearth | Difficulty: MEDIUM
Tags: String algorithms


Solutions:
class Node:
	def __init__(self, word, weight):
		self.sub_nodes = {}
		self.weight = weight
		self.str = word

	def add(self, word, weight):
		current_node = self
		while True:
			old_weight = current_node.weight
			if current_node.weight < weight:
				current_node.weight = weight
			common_len = 0
			for a, b in zip(current_node.str, word):
				if a != b:
					break
				common_len += 1
			if len(word) == common_len:
				return
			# Splits the current node when needed
			if len(current_node.str) > common_len:
				split_node = Node(current_node.str[common_len:], old_weight)
				split_node.sub_nodes = current_node.sub_nodes
				current_node.sub_nodes = {split_node.str[0]: split_node}
				current_node.str = current_node.str[:common_len]
				sub_node = None
			else:
				sub_node = current_node.sub_nodes.get(word[common_len])
			if sub_node is None:
				current_node.sub_nodes[word[common_len]] = Node(word[common_len:], weight)
				return
			word = word[common_len:]
			current_node = sub_node


def add_nodes():
	for ni in range(n):
		s, ws = (s for s in input().split())
		node.add(s, int(ws))


def search_tree():
	query = input()
	current_node = node
	while True:
		if len(query) <= len(current_node.str):
			if not current_node.str.startswith(query):
				return -1
			return current_node.weight
		if not query.startswith(current_node.str):
			return -1
		sub_node = current_node.sub_nodes.get(query[len(current_node.str)])
		if sub_node is None:
			return -1
		query = query[len(current_node.str):]
		current_node = sub_node


n, q = (int(s) for s in input().split())
node = Node("", 0)
add_nodes()
for qi in range(q):
	result_weight = search_tree()
	print(result_weight)


class Node:
	def __init__(self):
		self.max_w = -1
		self.edges = {}

def add(root, word, w):
	
	node = root
	for l in word:
		
		if node.max_w < w:
			node.max_w = w
			
		if l in node.edges:
			node = node.edges[l]
		else:
			node.edges[l] = Node()
			node = node.edges[l]
	
	if node.max_w < w:
			node.max_w = w

def find_max(root, prefix):
	node = root
	for l in prefix:
		if l in node.edges:
			node = node.edges[l]
		else:
			return -1
	
	return node.max_w

n, q = list(map(int, input().split()))
root = Node()
for i in range(n):
	word, w = input().split()
	w = int(w)
	add(root, word, w)

for i in range(q):
	prefix = input()
	print(find_max(root, prefix))
		


import fileinput

class Node(object):
	def __init__(self,data):
		self.data=data
		self.children={} # {'data' => Node}
		self.max_score =0
		
	def add_child(self,data,score):
		if data in self.children:
			pass
		else:
			self.children[data]=Node(data)
		self.children[data].max_score= score
		return self.children[data]
	
	def is_leaf(self):
		return len(self.children) == 0 and self.data != ""
	
	def __str__(self, *args, **kwargs):
		return self.data
	
class Trie(object):
	def __init__(self):
		self.root= Node("")
		
	def add_string(self,string, score):
		node, end_index = self.find_path(string,score)
		length= len(string)
		
		for i in range(end_index,length):
			if node.max_score < score:
				node.max_score = score
			node= node.add_child(string[i], score)
		node.add_child(score,score)

	# return node
	def find_path(self, string, score):
		node= self.root
		i= 0
		for c in string:
			if c in node.children:
				i=i+1
				if score != -1:
					if node.max_score < score:
						node.max_score = score   
				node=node.children[c]              
			else:
				break
		return node, i
	
	def max(self,node):
		pass
		
if __name__=="__main__":
	f= fileinput.input()
	n,q = list(map(int,f.readline().split(" ")))
	
	trie= Trie()
	
	while n > 0:
		n=n-1
		line, score=f.readline().strip().split(" ")
		trie.add_string(line, int(score))
	
	while q> 0:
		q=q-1
		query= f.readline().strip()
		length = len(query)
		node, end_index = trie.find_path(query,-1)
		if end_index==0 or end_index < length:
			print(-1)
		else:
			print(node.max_score)
		


class Node:
	def __init__(self):
		self.maxW = -1
		self.nxt = [None]*128

class Trie:
	def __init__(self):
		self.T = [Node()]

	def add(self, word, weight):
		v = 0
		for char in word:
			if not self.T[v].nxt[ord(char)]:
				self.T[v].nxt[ord(char)] = len(self.T)
				self.T.append(Node())
			self.T[v].maxW = max(self.T[v].maxW, weight)
			v = self.T[v].nxt[ord(char)]
		self.T[v].maxW = max(self.T[v].maxW, weight)

	def query(self, word):
		v = 0
		for char in word:
			if not self.T[v].nxt[ord(char)]:
				return -1
			v = self.T[v].nxt[ord(char)]
		return self.T[v].maxW


N, Q = list(map(int, input().split()))
T = Trie()
for _ in range(N):
	s, weight = input().split()
	T.add(s, int(weight))
for _ in range(Q):
	print(T.query(input()))