






"""simple docstring"""



def      _lowerCAmelCase		(							UpperCAmelCase__       :					str,						UpperCAmelCase__       :					str      )		->bool:
						A__						:  Optional[int]		  =  len(UpperCAmelCase__      ) + 1
						A__						:  Dict		  =  len(UpperCAmelCase__      ) + 1

						# dp is a 2d matrix where dp[i][j] denotes whether prefix string of
						# length i of input_string matches with prefix string of length j of
						# given pattern.
						# "dp" stands for dynamic programming.
						A__						:  List[str]		  =  [[0 for i in range(UpperCAmelCase__      )] for j in range(UpperCAmelCase__      )]

						# since string of zero length match pattern of zero length
						A__						:  Tuple		  =  1

						# since pattern of zero length will never match with string of non-zero length
						for i in range(1,						UpperCAmelCase__      ):
												A__						:  Dict		  =  0

						# since string of zero length will match with pattern where there
						# is at least one * alternatively
						for j in range(1,						UpperCAmelCase__      ):
												A__						:  Dict		  =  dp[0][j - 2] if pattern[j - 1] == """*""" else 0

						# now using bottom-up approach to find for all remaining lengths
						for i in range(1,						UpperCAmelCase__      ):
												for j in range(1,						UpperCAmelCase__      ):
																		if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
																								A__						:  Any		  =  dp[i - 1][j - 1]

																		elif pattern[j - 1] == "*":
																								if dp[i][j - 2] == 1:
																														A__						:  str		  =  1
																								elif pattern[j - 2] in (input_string[i - 1], "."):
																														A__						:  Tuple		  =  dp[i - 1][j]
																								else:
																														A__						:  str		  =  0
																		else:
																								A__						:  str		  =  0

						return bool(dp[-1][-1]      )


if __name__ == "__main__":
						import doctest

						doctest.testmod()
						# inputing the strings
						# input_string = input("input a string :")
						# pattern = input("input a pattern :")

						A_    =							'''aab'''
						A_    =							'''c*a*b'''

						# using function to check whether given string matches the given pattern
						if match_pattern(input_string, pattern):
												print(F'{input_string} matches the given pattern {pattern}')
						else:
												print(F'{input_string} does not match with the given pattern {pattern}')








"""simple docstring"""



from timeit import timeit




def      _lowerCAmelCase		(							UpperCAmelCase__       :					int      )		->int:
						if number < 0:
												raise ValueError("""the value of input must not be negative"""      )
						A__						:  Optional[int]		  =  0
						while number:
												number &= number - 1
												result += 1
						return result




def      _lowerCAmelCase		(							UpperCAmelCase__       :					int      )		->int:
						if number < 0:
												raise ValueError("""the value of input must not be negative"""      )
						A__						:  Tuple		  =  0
						while number:
												if number % 2 == 1:
																		result += 1
												number >>= 1
						return result




def      _lowerCAmelCase		(							)		->None:

						def do_benchmark(UpperCAmelCase__       :					int      ) -> None:
												A__						:  Optional[int]		  =  """import __main__ as z"""
												print(f'Benchmark when {number = }:'      )
												print(f'{get_set_bits_count_using_modulo_operator(UpperCAmelCase__      ) = }'      )
												A__						:  Any		  =  timeit("""z.get_set_bits_count_using_modulo_operator(25)""",						setup=UpperCAmelCase__      )
												print(f'timeit() runs in {timing} seconds'      )
												print(f'{get_set_bits_count_using_brian_kernighans_algorithm(UpperCAmelCase__      ) = }'      )
												A__						:  List[str]		  =  timeit(
												    """z.get_set_bits_count_using_brian_kernighans_algorithm(25)""",						setup=UpperCAmelCase__,						)
												print(f'timeit() runs in {timing} seconds'      )

						for number in (2_5, 3_7, 5_8, 0):
												do_benchmark(UpperCAmelCase__      )
												print()


if __name__ == "__main__":
						import doctest

						doctest.testmod()
						benchmark()






