strings.booths_algorithm

Attributes

ba

Classes

BoothsAlgorithm

Booth's Algorithm finds the lexicographically minimal rotation of a string.

Module Contents

class strings.booths_algorithm.BoothsAlgorithm

Booth’s Algorithm finds the lexicographically minimal rotation of a string.

Time Complexity: O(n) - Linear time where n is the length of input string Space Complexity: O(n) - Linear space for failure function array

For More Visit - https://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm

find_minimal_rotation(string: str) → str

Find the lexicographically minimal rotation of the input string.

Args:

string (str): Input string to find minimal rotation.

Returns:

str: Lexicographically minimal rotation of the input string.

Raises:

ValueError: If the input is not a string or is empty.

Examples:

>>> ba = BoothsAlgorithm()
>>> ba.find_minimal_rotation("baca")
'abac'
>>> ba.find_minimal_rotation("aaab")
'aaab'
>>> ba.find_minimal_rotation("abcd")
'abcd'
>>> ba.find_minimal_rotation("dcba")
'adcb'
>>> ba.find_minimal_rotation("aabaa")
'aaaab'

strings.booths_algorithm.ba