


__snake_case		:Any   	=  256
# Modulus to hash a string
__snake_case		:List[Any]   	=  100_0003





def   __snake_case			(    _UpperCAmelCase     ,				_UpperCAmelCase       ):
    __a		 =       len(_UpperCAmelCase       )
    __a		 =       len(_UpperCAmelCase       )
    if p_len > t_len:
        return False

    __a		 =       0
    __a		 =       0
    __a		 =       1

    # Calculating the hash of pattern and substring of text
    for i in range(_UpperCAmelCase       ):
        __a		 =       (ord(pattern[i]       ) + p_hash * alphabet_size) % modulus
        __a		 =       (ord(text[i]       ) + text_hash * alphabet_size) % modulus
        if i == p_len - 1:
            continue
        __a		 =       (modulus_power * alphabet_size) % modulus

    for i in range(0     ,				t_len - p_len + 1       ):
        if text_hash == p_hash and text[i : i + p_len] == pattern:
            return True
        if i == t_len - p_len:
            continue
        # Calculate the https://en.wikipedia.org/wiki/Rolling_hash
        __a		 =       (
            (text_hash - ord(text[i]       ) * modulus_power) * alphabet_size
            + ord(text[i + p_len]       )
        ) % modulus
    return False





def   __snake_case			(    ):
    __a		 =       '''abc1abc12'''
    __a		 =       '''alskfjaldsabc1abc1abc12k23adsfabcabc'''
    __a		 =       '''alskfjaldsk23adsfabcabc'''
    assert rabin_karp(_UpperCAmelCase     ,				_UpperCAmelCase       ) and not rabin_karp(_UpperCAmelCase     ,				_UpperCAmelCase       )

    # Test 2)
    __a		 =       '''ABABX'''
    __a		 =       '''ABABZABABYABABX'''
    assert rabin_karp(_UpperCAmelCase     ,				_UpperCAmelCase       )

    # Test 3)
    __a		 =       '''AAAB'''
    __a		 =       '''ABAAAAAB'''
    assert rabin_karp(_UpperCAmelCase     ,				_UpperCAmelCase       )

    # Test 4)
    __a		 =       '''abcdabcy'''
    __a		 =       '''abcxabcdabxabcdabcdabcy'''
    assert rabin_karp(_UpperCAmelCase     ,				_UpperCAmelCase       )

    # Test 5)
    __a		 =       '''Lü'''
    __a		 =       '''Lüsai'''
    assert rabin_karp(_UpperCAmelCase     ,				_UpperCAmelCase       )
    __a		 =       '''Lue'''
    assert not rabin_karp(_UpperCAmelCase     ,				_UpperCAmelCase       )
    print('''Success.'''       )


if __name__ == "__main__":
 test_rabin_karp()










from __future__ import annotations





def   __snake_case			(    _UpperCAmelCase     ,				_UpperCAmelCase       ):
    print(f'Vertex\tShortest Distance from vertex {src}'       )
    for i, d in enumerate(_UpperCAmelCase       ):
        print(f'{i}\t\t{d}'       )





def   __snake_case			(    _UpperCAmelCase     ,				_UpperCAmelCase     ,				_UpperCAmelCase       ):
    for j in range(_UpperCAmelCase       ):
        __a ,     __a ,     __a		 =       (graph[j][k] for k in ['''src''', '''dst''', '''weight'''])
        if distance[u] != float('''inf'''       ) and distance[u] + w < distance[v]:
            return True
    return False





def   __snake_case			(    _UpperCAmelCase     ,				_UpperCAmelCase     ,				_UpperCAmelCase     ,				_UpperCAmelCase       ):
    __a		 =       [float('''inf'''       )] * vertex_count
    __a		 =       0.0

    for _ in range(vertex_count - 1       ):
        for j in range(_UpperCAmelCase       ):
            __a ,     __a ,     __a		 =       (graph[j][k] for k in ['''src''', '''dst''', '''weight'''])

            if distance[u] != float('''inf'''       ) and distance[u] + w < distance[v]:
                __a		 =       distance[u] + w

    __a		 =       check_negative_cycle(_UpperCAmelCase     ,				_UpperCAmelCase     ,				_UpperCAmelCase       )
    if negative_cycle_exists:
        raise Exception('''Negative cycle found'''       )

    return distance


if __name__ == "__main__":
 import doctest

 doctest.testmod()

 __snake_case		:Dict   	=  int(input('''Enter number of vertices: ''').strip())
 __snake_case		:Any   	=  int(input('''Enter number of edges: ''').strip())

 __snake_case		:list[dict[str, int]]   	=  [{} for _ in range(E)]

 for i in range(E):
  print('''Edge ''', i + 1)
  __snake_case	,__snake_case	,__snake_case		:int   	=  (
      int(x)
      for x in input('''Enter source, destination, weight: ''').strip().split(''' ''')
  )
  __snake_case		:Any   	=  {'''src''': src, '''dst''': dest, '''weight''': weight}

 __snake_case		:List[str]   	=  int(input('''\nEnter shortest path source:''').strip())
 __snake_case		:Optional[Any]   	=  bellman_ford(graph, V, E, source)
 print_distance(shortest_distance, 0)





