class 	lowerCamelCase_     :






    '''simple docstring'''






    def __init__(	self , __lowercase , __lowercase=None , __lowercase=None)       ->	int:
        __UpperCamelCase     :Optional[Any]			  =		data
        __UpperCamelCase     :Union[str, Any]			  =		previous
        __UpperCamelCase     :List[str]			  =		next_node







    def __str__(	self)       ->	str:
        return f"""{self.data}"""







    def 			UpperCamelCase__   (	self)       ->	int:
        return self.data







    def 			UpperCamelCase__   (	self)       ->	Optional[Any]:
        return self.next







    def 			UpperCamelCase__   (	self)       ->	Dict:
        return self.previous


class 	lowerCamelCase_     :






    '''simple docstring'''






    def __init__(	self , __lowercase)       ->	Dict:
        __UpperCamelCase     :List[Any]			  =		head







    def __iter__(	self)       ->	List[str]:
        return self







    def 			UpperCamelCase__   (	self)       ->	Optional[Any]:
        if not self.current:
            raise StopIteration
        else:
            __UpperCamelCase     :str			  =		self.current.get_data()
            __UpperCamelCase     :Optional[int]			  =		self.current.get_next()
            return value


class 	lowerCamelCase_     :






    '''simple docstring'''






    def __init__(	self)       ->	List[str]:
        __UpperCamelCase     :Any			  =		None  # First node in list
        __UpperCamelCase     :Union[str, Any]			  =		None  # Last node in list







    def __str__(	self)       ->	Any:
        __UpperCamelCase     :Optional[int]			  =		self.head
        __UpperCamelCase     :Union[str, Any]			  =		[]
        while current is not None:
            nodes.append(current.get_data())
            __UpperCamelCase     :List[str]			  =		current.get_next()
        return " ".join(str(__lowercase) for node in nodes)







    def __contains__(	self , __lowercase)       ->	List[str]:
        __UpperCamelCase     :int			  =		self.head
        while current:
            if current.get_data() == value:
                return True
            __UpperCamelCase     :List[Any]			  =		current.get_next()
        return False







    def __iter__(	self)       ->	Dict:
        return LinkedListIterator(self.head)







    def 			UpperCamelCase__   (	self)       ->	Dict:
        if self.head:
            return self.head.get_data()
        return None







    def 			UpperCamelCase__   (	self)       ->	Dict:
        if self.tail:
            return self.tail.get_data()
        return None







    def 			UpperCamelCase__   (	self , __lowercase)       ->	None:
        if self.head is None:
            __UpperCamelCase     :Any			  =		node
            __UpperCamelCase     :Any			  =		node
        else:
            self.insert_before_node(self.head , __lowercase)







    def 			UpperCamelCase__   (	self , __lowercase)       ->	None:
        if self.head is None:
            self.set_head(__lowercase)
        else:
            self.insert_after_node(self.tail , __lowercase)







    def 			UpperCamelCase__   (	self , __lowercase)       ->	None:
        __UpperCamelCase     :Any			  =		Node(__lowercase)
        if self.head is None:
            self.set_head(__lowercase)
        else:
            self.set_tail(__lowercase)







    def 			UpperCamelCase__   (	self , __lowercase , __lowercase)       ->	None:
        __UpperCamelCase     :Tuple			  =		node
        __UpperCamelCase     :Dict			  =		node.previous

        if node.get_previous() is None:
            __UpperCamelCase     :Any			  =		node_to_insert
        else:
            __UpperCamelCase     :str			  =		node_to_insert

        __UpperCamelCase     :List[str]			  =		node_to_insert







    def 			UpperCamelCase__   (	self , __lowercase , __lowercase)       ->	None:
        __UpperCamelCase     :Union[str, Any]			  =		node
        __UpperCamelCase     :int			  =		node.next

        if node.get_next() is None:
            __UpperCamelCase     :Dict			  =		node_to_insert
        else:
            __UpperCamelCase     :int			  =		node_to_insert

        __UpperCamelCase     :int			  =		node_to_insert







    def 			UpperCamelCase__   (	self , __lowercase , __lowercase)       ->	None:
        __UpperCamelCase     :Tuple			  =		1
        __UpperCamelCase     :List[str]			  =		Node(__lowercase)
        __UpperCamelCase     :List[str]			  =		self.head
        while node:
            if current_position == position:
                self.insert_before_node(__lowercase , __lowercase)
                return
            current_position += 1
            __UpperCamelCase     :List[str]			  =		node.next
        self.insert_after_node(self.tail , __lowercase)







    def 			UpperCamelCase__   (	self , __lowercase)       ->	Node:
        __UpperCamelCase     :List[Any]			  =		self.head
        while node:
            if node.get_data() == item:
                return node
            __UpperCamelCase     :str			  =		node.get_next()
        raise Exception('''Node not found''')







    def 			UpperCamelCase__   (	self , __lowercase)       ->	Union[str, Any]:
        if (node := self.get_node(__lowercase)) is not None:
            if node == self.head:
                __UpperCamelCase     :Union[str, Any]			  =		self.head.get_next()

            if node == self.tail:
                __UpperCamelCase     :Optional[int]			  =		self.tail.get_previous()

            self.remove_node_pointers(__lowercase)







    @staticmethod
    def 			UpperCamelCase__   (	__lowercase)       ->	None:
        if node.get_next():
            __UpperCamelCase     :str			  =		node.previous

        if node.get_previous():
            __UpperCamelCase     :List[str]			  =		node.next

        __UpperCamelCase     :int			  =		None
        __UpperCamelCase     :int			  =		None







    def 			UpperCamelCase__   (	self)       ->	Tuple:
        return self.head is None



def lowerCamelCase  (   ):
    '''simple docstring'''









if __name__ == "__main__":
    import doctest

    doctest.testmod()






def lowerCamelCase  (   SCREAMING_SNAKE_CASE	):
    '''simple docstring'''







    __UpperCamelCase     :Tuple			  =		[0 for i in range(len(SCREAMING_SNAKE_CASE	)	)]

    # initialize interval's left pointer and right pointer
    __UpperCamelCase  ,       __UpperCamelCase     :str			  =		0, 0

    for i in range(1  ,			len(SCREAMING_SNAKE_CASE	)	):
        # case when current index is inside the interval
        if i <= right_pointer:
            __UpperCamelCase     :Union[str, Any]			  =		min(right_pointer - i + 1  ,			z_result[i - left_pointer]	)
            __UpperCamelCase     :Tuple			  =		min_edge

        while go_next(SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE	):
            z_result[i] += 1

        # if new index's result gives us more right interval,
        # we've to update left_pointer and right_pointer
        if i + z_result[i] - 1 > right_pointer:
            __UpperCamelCase  ,       __UpperCamelCase     :Union[str, Any]			  =		i, i + z_result[i] - 1

    return z_result



def lowerCamelCase  (   SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE	):
    '''simple docstring'''







    return i + z_result[i] < len(SCREAMING_SNAKE_CASE	) and s[z_result[i]] == s[i + z_result[i]]



def lowerCamelCase  (   SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE	):
    '''simple docstring'''







    __UpperCamelCase     :List[Any]			  =		0
    # concatenate 'pattern' and 'input_str' and call z_function
    # with concatenated string
    __UpperCamelCase     :Tuple			  =		z_function(pattern + input_str	)

    for val in z_result:
        # if value is greater then length of the pattern string
        # that means this index is starting position of substring
        # which is equal to pattern string
        if val >= len(SCREAMING_SNAKE_CASE	):
            answer += 1

    return answer


if __name__ == "__main__":
    import doctest

    doctest.testmod()





