<p>Given a binary tree <code>root</code> and a&nbsp;linked list with&nbsp;<code>head</code>&nbsp;as the first node.&nbsp;</p>

<p>Return True if all the elements in the linked list starting from the <code>head</code> correspond to some <em>downward path</em> connected in the binary tree&nbsp;otherwise return False.</p>

<p>In this context downward path means a path that starts at some node and goes downwards.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2020/02/12/sample_1_1720.png" style="width: 220px; height: 280px;" /></strong></p>

<pre>
<strong>Input:</strong> head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
<strong>Output:</strong> true
<strong>Explanation:</strong> Nodes in blue form a subpath in the binary Tree.  
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2020/02/12/sample_2_1720.png" style="width: 220px; height: 280px;" /></strong></p>

<pre>
<strong>Input:</strong> head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
<strong>Output:</strong> false
<strong>Explanation:</strong> There is no path in the binary tree that contains all the elements of the linked list from <code>head</code>.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree will be in the range <code>[1, 2500]</code>.</li>
	<li>The number of nodes in the list will be in the range <code>[1, 100]</code>.</li>
	<li><code>1 &lt;= Node.val&nbsp;&lt;= 100</code>&nbsp;for each node in the linked list and binary tree.</li>
</ul>

'''
==================================================
Notes
- the head-node comparison can start anywhere in the given tree, not just at the root

GOOD TESTCASES
- for KMP, shows how backtracking works for prefix_table
[1,2,3,1,2,3]
[1,2,2,null,2,3,null,1,null,1,1,null,null,null,null,1,2,null,null,3]

DFS
- here we use two recursive functions
    - 1: dfs the given tree to see if a path exists that starts at the root of the tree
    - 2: find a path that exists below the root
- we can use the given function signature for the 1st recursive function
- use a recursive function to dfs the given binary tree ->
    - params
        - t_node -> current tree node
        - l_node -> current linked list node
    - base case
        - if l_node is null -> return True
        - if t_node is null -> return False
    - logic
        - if t_node does not match l_node -> return False
        - otherwise -> return search for left or right node
- Time -> O(n * m)
- Space -> O(n + m)

Knuth-Morris-Pratt (KMP)
- improve DFS using KMP's concept of string matching
- use an array to store each list node's value -> pattern
- use an integer to keep track of the position in pattern -> pattern_index
- use an array to store the correct index to backtrack to when a node's value does not match pattern_index -> prefix_table
- iterate head to update pattern and prefix_table ->
- use a recursive function to find the pattern in root ->
- Time -> O(m + n)
- Space -> O(m + n)

==================================================
'''

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        return self.kmp_algo(head, root)

    def dfs(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        def search(t_node: Optional[TreeNode], l_node: Optional[ListNode]):
            if not l_node:
                return True

            if not t_node or t_node.val != l_node.val:
                return False

            return search(t_node.left, l_node.next) or search(t_node.right, l_node.next)

        if not root:
            return False
        if search(root, head):
            return True
        return self.dfs(head, root.left) or self.dfs(head, root.right)

    def kmp_algo(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        def search(node: Optional[TreeNode], pattern_index: int, pattern: List[int], prefix_table: List[int]):
            if not node:
                return False

            while pattern_index > 0 and node.val != pattern[pattern_index]:
                pattern_index = prefix_table[pattern_index - 1]

            if node.val == pattern[pattern_index]:
                pattern_index += 1
            
            # check if pattern is fully matched
            if pattern_index == len(pattern):
                return True

            # recursively search left and right subtrees
            return search(node.left, pattern_index, pattern, prefix_table) or\
                search(node.right, pattern_index, pattern, prefix_table)

        ### build the pattern and prefix table from the linked list
        pattern = [head.val]
        prefix_table = [0]
        pattern_index = 0
        head = head.next

        while head:
            while pattern_index > 0 and head.val != pattern[pattern_index]:
                pattern_index = prefix_table[pattern_index - 1]

            if head.val == pattern[pattern_index]:
                pattern_index += 1

            pattern.append(head.val)
            prefix_table.append(pattern_index)
            head = head.next

        ### perform DFS to search for the pattern in the tree
        return search(root, 0, pattern, prefix_table)
48