'''simple docstring'''

def 			__UpperCamelCase       (   UpperCAmelCase     ):
 lowercase__				:    Optional[Any]  =					[0 for i in range(len(UpperCAmelCase     )     )]

 # initialize interval's left pointer and right pointer
 lowercase__ ,							lowercase__				:    Optional[Any]  =					0, 0

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

  while go_next(UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase     ):
   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:
   lowercase__ ,							lowercase__				:    Tuple  =					i, i + z_result[i] - 1

 return z_result
def 			__UpperCamelCase       (   UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase     ):
 return i + z_result[i] < len(UpperCAmelCase     ) and s[z_result[i]] == s[i + z_result[i]]
def 			__UpperCamelCase       (   UpperCAmelCase		,     UpperCAmelCase     ):
 lowercase__				:    Any  =					0
 # concatenate 'pattern' and 'input_str' and call z_function
 # with concatenated string
 lowercase__				:    Dict  =					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(UpperCAmelCase     ):
   answer += 1

 return answer


if __name__ == "__main__":
  import doctest

  doctest.testmod()


'''simple docstring'''

import unittest

from knapsack import knapsack as k



class 			UpperCAmelCase  (						unittest.TestCase					):





       '''simple docstring'''



       def _lowerCAmelCase(						self )  ->  Tuple:
        lowercase__				:    Optional[Any]  =					0
        lowercase__				:    Any  =					[0]
        lowercase__				:    List[Any]  =					[0]
        lowercase__				:    Optional[Any]  =					len(__lowerCAmelCase )
        self.assertEqual(k.knapsack(__lowerCAmelCase	,   __lowerCAmelCase	,   __lowerCAmelCase	,   __lowerCAmelCase )	,   0 )

        lowercase__				:    List[str]  =					[60]
        lowercase__				:    List[str]  =					[10]
        lowercase__				:    List[str]  =					len(__lowerCAmelCase )
        self.assertEqual(k.knapsack(__lowerCAmelCase	,   __lowerCAmelCase	,   __lowerCAmelCase	,   __lowerCAmelCase )	,   0 )

       def _lowerCAmelCase(						self )  ->  Optional[Any]:
        lowercase__				:    Optional[Any]  =					3
        lowercase__				:    List[Any]  =					[1, 2, 3]
        lowercase__				:    Union[str, Any]  =					[3, 2, 1]
        lowercase__				:    List[Any]  =					len(__lowerCAmelCase )
        self.assertEqual(k.knapsack(__lowerCAmelCase	,   __lowerCAmelCase	,   __lowerCAmelCase	,   __lowerCAmelCase )	,   5 )


       def _lowerCAmelCase(						self )  ->  Optional[Any]:
        lowercase__				:    int  =					50
        lowercase__				:    Any  =					[60, 100, 120]
        lowercase__				:    int  =					[10, 20, 30]
        lowercase__				:    Optional[Any]  =					len(__lowerCAmelCase )
        self.assertEqual(k.knapsack(__lowerCAmelCase	,   __lowerCAmelCase	,   __lowerCAmelCase	,   __lowerCAmelCase )	,   220 )


if __name__ == "__main__":
  unittest.main()

