
from __future__ import annotations

from collections import deque

class       a		:







							def __init__(						self  :  Any      ,				snake_case__  :  list[str] ):
								"""simple docstring"""







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

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







							def       UpperCAmelCase__					(						self  :  Optional[Any]      ,				snake_case__  :  int      ,				snake_case__  :  str ):
								"""simple docstring"""







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







							def       UpperCAmelCase__					(						self  :  Dict      ,				snake_case__  :  str ):
								"""simple docstring"""







								__lowerCAmelCase         =							0
								for character in keyword:
									__lowerCAmelCase         =							self.find_next_state(snake_case__      ,				snake_case__ )
									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 )
										__lowerCAmelCase         =							len(self.adlist ) - 1
									else:
										__lowerCAmelCase         =							next_state
								self.adlist[current_state]["output"].append(snake_case__ )







							def       UpperCAmelCase__					(						self  :  int ):
								"""simple docstring"""







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







							def       UpperCAmelCase__					(						self  :  List[Any]      ,				snake_case__  :  str ):
								"""simple docstring"""







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


if __name__ == "__main__":
					import doctest

					doctest.testmod()








import numpy as np
import qiskit






def 		_UpperCAmelCase   (	UpperCamelCase:     int = 8			,							UpperCamelCase:     int | None = None  ):






	"""simple docstring"""


	__lowerCAmelCase         =							np.random.default_rng(seed=UpperCamelCase  )

	# Roughly 25% of the qubits will contribute to the key.
	# So we take more than we need.
	__lowerCAmelCase         =							6 * key_len
	# Measurement basis for Alice's qubits.
	__lowerCAmelCase         =							rng.integers(2			,							size=UpperCamelCase  )
	# The set of states Alice will prepare.
	__lowerCAmelCase         =							rng.integers(2			,							size=UpperCamelCase  )
	# Measurement basis for Bob's qubits.
	__lowerCAmelCase         =							rng.integers(2			,							size=UpperCamelCase  )

	# Quantum Circuit to simulate BB84
	__lowerCAmelCase         =							qiskit.QuantumCircuit(UpperCamelCase			,							name="BB84"  )

	# Alice prepares her qubits according to rules above.
	for index, _ in enumerate(UpperCamelCase  ):
		if alice_state[index] == 1:
			bbaa_circ.x(UpperCamelCase  )
		if alice_basis[index] == 1:
			bbaa_circ.h(UpperCamelCase  )
	bbaa_circ.barrier()

	# Bob measures the received qubits according to rules above.
	for index, _ in enumerate(UpperCamelCase  ):
		if bob_basis[index] == 1:
			bbaa_circ.h(UpperCamelCase  )

	bbaa_circ.barrier()
	bbaa_circ.measure_all()

	# Simulate the quantum circuit.
	__lowerCAmelCase         =							qiskit.Aer.get_backend("aer_simulator"  )
	# We only need to run one shot because the key is unique.
	# Multiple shots will produce the same key.
	__lowerCAmelCase         =							qiskit.execute(UpperCamelCase			,							UpperCamelCase			,							shots=1			,							seed_simulator=UpperCamelCase  )
	# Returns the result of measurement.
	__lowerCAmelCase         =							job.result().get_counts(UpperCamelCase  ).most_frequent()

	# Extracting the generated key from the simulation results.
	# Only keep measurement results where Alice and Bob chose the same basis.
	__lowerCAmelCase         =							"".join(
	    [
	        result_bit
	        for alice_basis_bit, bob_basis_bit, result_bit in zip(
	            UpperCamelCase			,							UpperCamelCase			,							UpperCamelCase  )
	        if alice_basis_bit == bob_basis_bit
	    ]  )

	# Get final key. Pad with 0 if too short, otherwise truncate.
	__lowerCAmelCase         =							gen_key[:key_len] if len(UpperCamelCase  ) >= key_len else gen_key.ljust(UpperCamelCase			,							"0"  )
	return key


if __name__ == "__main__":
					print(f'''The generated key is : {bbaa(8, seed=0)}''')
					from doctest import testmod

					testmod()






