<p>You are given a string <code>word</code> and an array of strings <code>forbidden</code>.</p>

<p>A string is called <strong>valid</strong> if none of its substrings are present in <code>forbidden</code>.</p>

<p>Return <em>the length of the <strong>longest valid substring</strong> of the string </em><code>word</code>.</p>

<p>A <strong>substring</strong> is a contiguous sequence of characters in a string, possibly empty.</p>

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

<pre>
<strong>Input:</strong> word = &quot;cbaaaabc&quot;, forbidden = [&quot;aaa&quot;,&quot;cb&quot;]
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 11 valid substrings in word: &quot;c&quot;, &quot;b&quot;, &quot;a&quot;, &quot;ba&quot;, &quot;aa&quot;, &quot;bc&quot;, &quot;baa&quot;, &quot;aab&quot;, &quot;ab&quot;, &quot;abc&quot; and &quot;aabc&quot;. The length of the longest valid substring is 4. 
It can be shown that all other substrings contain either &quot;aaa&quot; or &quot;cb&quot; as a substring. </pre>

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

<pre>
<strong>Input:</strong> word = &quot;leetcode&quot;, forbidden = [&quot;de&quot;,&quot;le&quot;,&quot;e&quot;]
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 11 valid substrings in word: &quot;l&quot;, &quot;t&quot;, &quot;c&quot;, &quot;o&quot;, &quot;d&quot;, &quot;tc&quot;, &quot;co&quot;, &quot;od&quot;, &quot;tco&quot;, &quot;cod&quot;, and &quot;tcod&quot;. The length of the longest valid substring is 4.
It can be shown that all other substrings contain either &quot;de&quot;, &quot;le&quot;, or &quot;e&quot; as a substring. 
</pre>

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

<ul>
	<li><code>1 &lt;= word.length &lt;= 10<sup>5</sup></code></li>
	<li><code>word</code> consists only of lowercase English letters.</li>
	<li><code>1 &lt;= forbidden.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= forbidden[i].length &lt;= 10</code></li>
	<li><code>forbidden[i]</code> consists only of lowercase English letters.</li>
</ul>

class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        s = set([])
 
        # Loop to traverse the string
        for i in range(len(word)):

            # Insert current character
            # into the set
            s.add(word[i])

        # Return Answer
        if len(s)==1 and len(word)>1000:
            return len(word)

 
        n = len(word)
        automaton = AhoCorasickAutomaton(forbidden)
        last_occurrence = [-1] * n
        node = automaton.root

        for i in range(n):
            while node and word[i] not in node.children:
                node = node.fail
            node = node.children[word[i]] if node else automaton.root
            temp = node
            while temp and temp != automaton.root:
                if temp.end:
                    last_occurrence[i] = max(last_occurrence[i], i - temp.length + 1)
                temp = temp.fail

        max_len = 0
        start = 0
        for end in range(n):
            while start <= last_occurrence[end]:
                start += 1
            max_len = max(max_len, end - start + 1)

        return max_len
class TrieNode:
    def __init__(self):
        self.children = {}
        self.fail = None
        self.end = False
        self.length = 0


class AhoCorasickAutomaton:
    def __init__(self, forbidden):
        self.root = TrieNode()
        self.forbidden = forbidden
        self.build_trie()
        self.build_failure_function()

    def build_trie(self):
        for word in self.forbidden:
            node = self.root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.end = True
            node.length = len(word)

    def build_failure_function(self):
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            for char, child in node.children.items():
                if node == self.root:
                    child.fail = self.root
                else:
                    fail = node.fail
                    while fail:
                        if char in fail.children:
                            child.fail = fail.children[char]
                            break
                        fail = fail.fail
                    if not fail:
                        child.fail = self.root
                queue.append(child)
2821