from __future__ import annotations



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: str				,  __UpperCamelCase					: str			)							->      bool:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__    							=   get_failure_array(__UpperCamelCase			)

  # 2) Step through text searching for pattern
  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__    							=   0, 0  # index into text, pattern
  while i < len(__UpperCamelCase			):
    if pattern[j] == text[i]:
      if j == (len(__UpperCamelCase			) - 1):
        return True
      j += 1

    # if this is a prefix in our pattern
    # just go back far enough to continue
    elif j > 0:
      SCREAMING_SNAKE_CASE__    							=   failure[j - 1]
      continue
    i += 1
  return False



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: str			)							->      list[int]:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__    							=   [0]
  SCREAMING_SNAKE_CASE__    							=   0
  SCREAMING_SNAKE_CASE__    							=   1
  while j < len(__UpperCamelCase			):
    if pattern[i] == pattern[j]:
      i += 1
    elif i > 0:
      SCREAMING_SNAKE_CASE__    							=   failure[i - 1]
      continue
    j += 1
    failure.append(__UpperCamelCase			)
  return failure


if __name__ == "__main__":
   # Test 1)
   __lowerCamelCase    :				Dict							     =	'''abc1abc12'''
   __lowerCamelCase    :				int							     =	'''alskfjaldsabc1abc1abc12k23adsfabcabc'''
   __lowerCamelCase    :				Optional[Any]							     =	'''alskfjaldsk23adsfabcabc'''
   assert kmp(pattern, texta) and not kmp(pattern, texta)

   # Test 2)
   __lowerCamelCase    :				List[str]							     =	'''ABABX'''
   __lowerCamelCase    :				List[str]							     =	'''ABABZABABYABABX'''
   assert kmp(pattern, text)

   # Test 3)
   __lowerCamelCase    :				List[str]							     =	'''AAAB'''
   __lowerCamelCase    :				str							     =	'''ABAAAAAB'''
   assert kmp(pattern, text)

   # Test 4)
   __lowerCamelCase    :				Any							     =	'''abcdabcy'''
   __lowerCamelCase    :				Optional[Any]							     =	'''abcxabcdabxabcdabcdabcy'''
   assert kmp(pattern, text)

   # Test 5)
   __lowerCamelCase    :				Any							     =	'''aabaabaaa'''
   assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]

import os

__lowerCamelCase    :				Union[str, Any]							     =	{'''I''': 1, '''V''': 5, '''X''': 10, '''L''': 50, '''C''': 100, '''D''': 500, '''M''': 1000}



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: str			)							->      int:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__    							=   0

  SCREAMING_SNAKE_CASE__    							=   0
  while index < len(__UpperCamelCase			) - 1:
    SCREAMING_SNAKE_CASE__    							=   SYMBOLS[numerals[index]]
    SCREAMING_SNAKE_CASE__    							=   SYMBOLS[numerals[index + 1]]
    if current_value < next_value:
      total_value -= current_value
    else:
      total_value += current_value
    index += 1
  total_value += SYMBOLS[numerals[index]]

  return total_value



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: int			)							->      str:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__    							=   """"""

  SCREAMING_SNAKE_CASE__    							=   num // 10_00
  numerals += m_count * "M"
  num %= 10_00

  SCREAMING_SNAKE_CASE__    							=   num // 1_00
  if c_count == 9:
    numerals += "CM"
    c_count -= 9
  elif c_count == 4:
    numerals += "CD"
    c_count -= 4
  if c_count >= 5:
    numerals += "D"
    c_count -= 5
  numerals += c_count * "C"
  num %= 1_00

  SCREAMING_SNAKE_CASE__    							=   num // 10
  if x_count == 9:
    numerals += "XC"
    x_count -= 9
  elif x_count == 4:
    numerals += "XL"
    x_count -= 4
  if x_count >= 5:
    numerals += "L"
    x_count -= 5
  numerals += x_count * "X"
  num %= 10

  if num == 9:
    numerals += "IX"
    num -= 9
  elif num == 4:
    numerals += "IV"
    num -= 4
  if num >= 5:
    numerals += "V"
    num -= 5
  numerals += num * "I"

  return numerals



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: str = "/p089_roman.txt"			)							->      int:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__    							=   0

  with open(os.path.dirname(__UpperCamelCase			) + roman_numerals_filename			) as filea:
    SCREAMING_SNAKE_CASE__    							=   filea.readlines()

  for line in lines:
    SCREAMING_SNAKE_CASE__    							=   line.strip()
    SCREAMING_SNAKE_CASE__    							=   parse_roman_numerals(__UpperCamelCase			)
    SCREAMING_SNAKE_CASE__    							=   generate_roman_numerals(__UpperCamelCase			)
    savings += len(__UpperCamelCase			) - len(__UpperCamelCase			)

  return savings


if __name__ == "__main__":
   print(F"""{solution() = }""")
