


'''simple docstring'''



from __future__ import annotations

from collections import deque



class 			a       :


     """simple docstring"""






     def __init__(       self  :	Dict							,				snake_case  :	list[str]    )		->							str:
          __UpperCAmelCase			:				list[dict]													=    []
          self.adlist.append(
              {'''value''': '''''', '''next_states''': [], '''fail_state''': 0, '''output''': []}    )

          for keyword in keywords:
               self.add_keyword(snake_case    )
          self.set_fail_transitions()

     def 				lowerCamelCase__				(       self  :	Optional[Any]							,				snake_case  :	int							,				snake_case  :	str    )		->							int | None:
          for state in self.adlist[current_state]["next_states"]:
               if char == self.adlist[state]["value"]:
                    return state
          return None

     def 				lowerCamelCase__				(       self  :	Union[str, Any]							,				snake_case  :	str    )		->							None:
          __UpperCAmelCase			:				Tuple													=    0
          for character in keyword:
               __UpperCAmelCase			:				Optional[int]													=    self.find_next_state(snake_case							,				snake_case    )
               if next_state is None:
                    self.adlist.append(
                        {
                            '''value''': character,
                            '''next_states''': [],
                            '''fail_state''': 0,
                            '''output''': [],
                        }    )
                    self.adlist[current_state]["next_states"].append(len(self.adlist    ) - 1    )
                    __UpperCAmelCase			:				Any													=    len(self.adlist    ) - 1
               else:
                    __UpperCAmelCase			:				List[Any]													=    next_state
          self.adlist[current_state]["output"].append(snake_case    )

     def 				lowerCamelCase__				(       self  :	List[str]    )		->							None:
          __UpperCAmelCase			:				deque													=    deque()
          for node in self.adlist[0]["next_states"]:
               q.append(snake_case    )
               __UpperCAmelCase			:				str													=    0
          while q:
               __UpperCAmelCase			:				int													=    q.popleft()
               for child in self.adlist[r]["next_states"]:
                    q.append(snake_case    )
                    __UpperCAmelCase			:				str													=    self.adlist[r]['''fail_state''']
                    while (
                        self.find_next_state(snake_case							,				self.adlist[child]['''value''']    ) is None
                        and state != 0
                    ):
                         __UpperCAmelCase			:				int													=    self.adlist[state]['''fail_state''']
                    __UpperCAmelCase			:				str													=    self.find_next_state(
                        snake_case							,				self.adlist[child]['''value''']    )
                    if self.adlist[child]["fail_state"] is None:
                         __UpperCAmelCase			:				Tuple													=    0
                    __UpperCAmelCase			:				List[str]													=    (
                        self.adlist[child]['''output''']
                        + self.adlist[self.adlist[child]['''fail_state''']]['''output''']
                    )






     def 				lowerCamelCase__				(       self  :	List[Any]							,				snake_case  :	str    )		->							dict[str, list[int]]:
          __UpperCAmelCase			:				dict													=    {}  # returns a dict with keywords and list of its occurrences
          __UpperCAmelCase			:				Optional[int]													=    0
          for i in range(len(snake_case    )    ):
               while (
                   self.find_next_state(snake_case							,				string[i]    ) is None
                   and current_state != 0
               ):
                    __UpperCAmelCase			:				int													=    self.adlist[current_state]['''fail_state''']
               __UpperCAmelCase			:				str													=    self.find_next_state(snake_case							,				string[i]    )
               if next_state is None:
                    __UpperCAmelCase			:				Dict													=    0
               else:
                    __UpperCAmelCase			:				Optional[int]													=    next_state
                    for key in self.adlist[current_state]["output"]:
                         if key not in result:
                              __UpperCAmelCase			:				str													=    []
                         result[key].append(i - len(snake_case    ) + 1    )
          return result


if __name__ == "__main__":
      import doctest

      doctest.testmod()








'''simple docstring'''



def 			_a			(		_lowercase      :			list[list[int]]    ,      _lowercase      :			int    ,      _lowercase      :			int    ,      _lowercase      :			set						):





     '''simple docstring'''






     __UpperCAmelCase							,     __UpperCAmelCase			:				Any													=    len(_lowercase						), len(grid[0]						)
     if (
         min(_lowercase    ,      _lowercase						) < 0
         or row == row_length
         or col == col_length
         or (row, col) in visit
         or grid[row][col] == 1
     ):
          return 0
     if row == row_length - 1 and col == col_length - 1:
          return 1

     visit.add((row, col)						)

     __UpperCAmelCase			:				Optional[Any]													=    0
     count += depth_first_search(_lowercase    ,      row + 1    ,      _lowercase    ,      _lowercase						)
     count += depth_first_search(_lowercase    ,      row - 1    ,      _lowercase    ,      _lowercase						)
     count += depth_first_search(_lowercase    ,      _lowercase    ,      col + 1    ,      _lowercase						)
     count += depth_first_search(_lowercase    ,      _lowercase    ,      col - 1    ,      _lowercase						)

     visit.remove((row, col)						)
     return count


if __name__ == "__main__":
      import doctest

      doctest.testmod()