



'''simple docstring'''





from __future__ import annotations
def        _SCREAMING_SNAKE_CASE  (	UpperCamelCase							,   UpperCamelCase      ):



    """simple docstring"""





    lowerCAmelCase__			:  Union[str, Any]											= get_failure_array(lowerCamelCase_      )

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

        # if this is a prefix in our pattern
        # just go back far enough to continue
        elif j > 0:
            lowerCAmelCase__			:  Tuple											= failure[j - 1]
            continue
        i += 1
    return False
def        _SCREAMING_SNAKE_CASE  (	UpperCamelCase      ):



    """simple docstring"""





    lowerCAmelCase__			:  Optional[Any]											= [0]
    lowerCAmelCase__			:  List[str]											= 0
    lowerCAmelCase__			:  Dict											= 1
    while j < len(lowerCamelCase_      ):
        if pattern[i] == pattern[j]:
            i += 1
        elif i > 0:
            lowerCAmelCase__			:  List[str]											= failure[i - 1]
            continue
        j += 1
        failure.append(lowerCamelCase_      )
    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]







'''simple docstring'''





import os
def        _SCREAMING_SNAKE_CASE  (	UpperCamelCase      ):



    """simple docstring"""





    lowerCAmelCase__			:  List[str]											= len(grid[0]      )
    lowerCAmelCase__			:  int											= len(UpperCamelCase      )

    lowerCAmelCase__			:  Optional[int]											= 0
    lowerCAmelCase__			:  Tuple											= 0
    lowerCAmelCase__			:  Optional[Any]											= 0

    # Check vertically, horizontally, diagonally at the same time (only works
    # for nxn grid)
    for i in range(UpperCamelCase      ):
        for j in range(n_rows - 3      ):
            lowerCAmelCase__			:  str											= grid[j][i] * grid[j + 1][i] * grid[j + 2][i] * grid[j + 3][i]
            lowerCAmelCase__			:  Optional[int]											= grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3]

            # Left-to-right diagonal (\) product
            if i < n_columns - 3:
                lowerCAmelCase__			:  Optional[int]											= (
                    grid[i][j]
                    * grid[i + 1][j + 1]
                    * grid[i + 2][j + 2]
                    * grid[i + 3][j + 3]
                )

            # Right-to-left diagonal(/) product
            if i > 2:
                lowerCAmelCase__			:  Tuple											= (
                    grid[i][j]
                    * grid[i - 1][j + 1]
                    * grid[i - 2][j + 2]
                    * grid[i - 3][j + 3]
                )

            lowerCAmelCase__			:  Dict											= max(
                UpperCamelCase							,   UpperCamelCase							,   UpperCamelCase							,   UpperCamelCase      )
            if max_product > largest:
                lowerCAmelCase__			:  Any											= max_product

    return largest
def        _SCREAMING_SNAKE_CASE  (	):



    """simple docstring"""





    lowerCAmelCase__			:  List[str]											= []
    with open(os.path.dirname(UpperCamelCase      ) + """/grid.txt"""      ) as file:
        for line in file:
            grid.append(line.strip("""\n"""      ).split(""" """      )      )

    lowerCAmelCase__			:  Dict											= [[int(UpperCamelCase      ) for i in grid[j]] for j in range(len(UpperCamelCase      )      )]

    return largest_product(UpperCamelCase      )


if __name__ == "__main__":
 print(solution())


