"""simple docstring"""





from __future__ import annotations

from itertools import permutations
from random import randint
from timeit import repeat





def 				a_     (      ):





       '''simple docstring'''

       lowercase__			:		Dict       =	[randint(-1000   , 1000     ) for i in range(10     )]
       lowercase__			:		List[Any]       =	randint(-5000   , 5000     )
       return (arr, r)


_UpperCamelCase   :						List[Any]      =    make_dataset()





def 				a_     (      _lowerCAmelCase  : list[int]   , _lowerCAmelCase  : int     ):





       '''simple docstring'''

       for triplet in permutations(_lowerCAmelCase   , 3     ):
              if sum(_lowerCAmelCase     ) == target:
                     return tuple(sorted(_lowerCAmelCase     )     )
       return (0, 0, 0)





def 				a_     (      _lowerCAmelCase  : list[int]   , _lowerCAmelCase  : int     ):





       '''simple docstring'''

       arr.sort()
       lowercase__			:		Optional[int]       =	len(_lowerCAmelCase     )
       for i in range(n - 1     ):
              lowercase__    ,      lowercase__			:		Tuple       =	i + 1, n - 1
              while left < right:
                     if arr[i] + arr[left] + arr[right] == target:
                            return (arr[i], arr[left], arr[right])
                     elif arr[i] + arr[left] + arr[right] < target:
                            left += 1
                     elif arr[i] + arr[left] + arr[right] > target:
                            right -= 1
       return (0, 0, 0)





def 				a_     (      ):





       '''simple docstring'''

       lowercase__			:		Any       =	'\nfrom __main__ import dataset, triplet_sum1, triplet_sum2\n'
       lowercase__			:		Union[str, Any]       =	'\ntriplet_sum1(*dataset)\n'
       lowercase__			:		Any       =	'\ntriplet_sum2(*dataset)\n'
       lowercase__			:		List[str]       =	repeat(setup=_lowerCAmelCase   , stmt=_lowerCAmelCase   , repeat=5   , number=1_0000     )
       lowercase__			:		Dict       =	repeat(setup=_lowerCAmelCase   , stmt=_lowerCAmelCase   , repeat=5   , number=1_0000     )
       return (min(_lowerCAmelCase     ), min(_lowerCAmelCase     ))


if __name__ == "__main__":
       from doctest import testmod

       testmod()
       _UpperCamelCase   :						List[Any]      =    solution_times()
       print(f'''The time for naive implementation is {times[0]}.''')
       print(f'''The time for optimized implementation is {times[1]}.''')





from __future__ import annotations







def        _lowerCamelCase(	lowercase__   , lowercase__	)						->	bool:

		'''simple docstring'''







		__lowercase=			get_failure_array(lowercase__	)

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

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







def        _lowerCamelCase(	lowercase__	)						->	list[int]:

		'''simple docstring'''







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


if __name__ == "__main__":
	# Test 1)
	lowerCAmelCase           =		'''abc1abc12'''
	lowerCAmelCase           =		'''alskfjaldsabc1abc1abc12k23adsfabcabc'''
	lowerCAmelCase           =		'''alskfjaldsk23adsfabcabc'''
	assert kmp(pattern, texta) and not kmp(pattern, texta)

	# Test 2)
	lowerCAmelCase           =		'''ABABX'''
	lowerCAmelCase           =		'''ABABZABABYABABX'''
	assert kmp(pattern, text)

	# Test 3)
	lowerCAmelCase           =		'''AAAB'''
	lowerCAmelCase           =		'''ABAAAAAB'''
	assert kmp(pattern, text)

	# Test 4)
	lowerCAmelCase           =		'''abcdabcy'''
	lowerCAmelCase           =		'''abcxabcdabxabcdabcdabcy'''
	assert kmp(pattern, text)

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






