



from __future__ import annotations

from collections import deque







class     __lowerCAmelCase					:

			'''simple docstring'''





			def __init__(		self     :						Tuple				,	A     :						list[str])     ->					Optional[int]:



						"""simple docstring"""






						_UpperCAmelCase	 =     []
						self.adlist.append(
						    {'value': '', 'next_states': [], 'fail_state': 0, 'output': []})

						for keyword in keywords:
									self.add_keyword(A)
						self.set_fail_transitions()



			def 					_lowerCamelCase (		self     :						int				,	A     :						int				,	A     :						str)     ->					int | None:



						"""simple docstring"""






						for state in self.adlist[current_state]["next_states"]:
									if char == self.adlist[state]["value"]:
												return state
						return None



			def 					_lowerCamelCase (		self     :						str				,	A     :						str)     ->					None:



						"""simple docstring"""






						_UpperCAmelCase	 =     0
						for character in keyword:
									_UpperCAmelCase	 =     self.find_next_state(A				,	A)
									if next_state is None:
												self.adlist.append(
												    {
												        'value': character,
												        'next_states': [],
												        'fail_state': 0,
												        'output': [],
												    })
												self.adlist[current_state]["next_states"].append(len(self.adlist) - 1)
												_UpperCAmelCase	 =     len(self.adlist) - 1
									else:
												_UpperCAmelCase	 =     next_state
						self.adlist[current_state]["output"].append(A)



			def 					_lowerCamelCase (		self     :						Any)     ->					None:



						"""simple docstring"""






						_UpperCAmelCase	 =     deque()
						for node in self.adlist[0]["next_states"]:
									q.append(A)
									_UpperCAmelCase	 =     0
						while q:
									_UpperCAmelCase	 =     q.popleft()
									for child in self.adlist[r]["next_states"]:
												q.append(A)
												_UpperCAmelCase	 =     self.adlist[r]["fail_state"]
												while (
												    self.find_next_state(A				,	self.adlist[child]['value']) is None
												    and state != 0
												):
															_UpperCAmelCase	 =     self.adlist[state]["fail_state"]
												_UpperCAmelCase	 =     self.find_next_state(
												    A				,	self.adlist[child]['value'])
												if self.adlist[child]["fail_state"] is None:
															_UpperCAmelCase	 =     0
												_UpperCAmelCase	 =     (
												    self.adlist[child]["output"]
												    + self.adlist[self.adlist[child]["fail_state"]]["output"]
												)



			def 					_lowerCamelCase (		self     :						int				,	A     :						str)     ->					dict[str, list[int]]:



						"""simple docstring"""






						_UpperCAmelCase	 =     {}  # returns a dict with keywords and list of its occurrences
						_UpperCAmelCase	 =     0
						for i in range(len(A)):
									while (
									    self.find_next_state(A				,	string[i]) is None
									    and current_state != 0
									):
												_UpperCAmelCase	 =     self.adlist[current_state]["fail_state"]
									_UpperCAmelCase	 =     self.find_next_state(A				,	string[i])
									if next_state is None:
												_UpperCAmelCase	 =     0
									else:
												_UpperCAmelCase	 =     next_state
												for key in self.adlist[current_state]["output"]:
															if key not in result:
																		_UpperCAmelCase	 =     []
															result[key].append(i - len(A) + 1)
						return result


if __name__ == "__main__":
							import doctest

							doctest.testmod()





import unittest

from knapsack import knapsack as k







class     __lowerCAmelCase					(    unittest.TestCase		):



			def 					_lowerCamelCase (		self     :						Optional[Any])     ->					Any:



						"""simple docstring"""






						_UpperCAmelCase	 =     0
						_UpperCAmelCase	 =     [0]
						_UpperCAmelCase	 =     [0]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	0)

						_UpperCAmelCase	 =     [60]
						_UpperCAmelCase	 =     [10]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	0)



			def 					_lowerCamelCase (		self     :						str)     ->					List[str]:



						"""simple docstring"""






						_UpperCAmelCase	 =     3
						_UpperCAmelCase	 =     [1, 2, 3]
						_UpperCAmelCase	 =     [3, 2, 1]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	5)



			def 					_lowerCamelCase (		self     :						Tuple)     ->					Tuple:



						"""simple docstring"""






						_UpperCAmelCase	 =     50
						_UpperCAmelCase	 =     [60, 1_00, 1_20]
						_UpperCAmelCase	 =     [10, 20, 30]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	2_20)


if __name__ == "__main__":
							unittest.main()
