<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>

from typing import List

def get_trie(patterns):
  trie = [{}]
  terminal = {}
  for k, pattern in enumerate(patterns):
    curr = 0
    for c in pattern:
      if c not in trie[curr]:
        trie.append({})
        trie[curr][c] = len(trie)-1
      curr = trie[curr][c]
    terminal[curr] = k
  return trie, terminal

def get_aho_corasick_automaton(trie, terminal):
  suffix = [-1] * len(trie)
  output = {}
  q = []
  for c in trie[0]:
    suffix[trie[0][c]] = 0
    q.append(trie[0][c])
  while q:
    nq = []
    for node in q:
      if suffix[node] in terminal:
        output[node] = suffix[node]
      elif suffix[node] in output:
        output[node] = output[suffix[node]]
      for c in trie[node]:
        nq.append(trie[node][c])
        curr = node
        while curr != 0:
          if c in trie[suffix[curr]]:
            suffix[trie[node][c]] = trie[suffix[curr]][c]
            break
          curr = suffix[curr]
        if suffix[trie[node][c]] == -1:
          suffix[trie[node][c]] = 0
    q = nq
  return suffix, output

def make_minimum_match_automaton(trie, terminal, output):
  q = [0]
  while q:
    nq = []
    for node in q:
      if node in output:
        output[node] = output[output[node]]
      elif node in terminal:
        output[node] = terminal[node]
      for c in trie[node]:
        nq.append(trie[node][c])
    q = nq

def get_minimum_matches(trie, suffix, output, t):
  curr, k = 0, 0
  while k < len(t):
    c = t[k] 
    if c not in trie[curr]:
      if curr != 0:
        curr = suffix[curr]
      else:
        k += 1
    else:
      curr = trie[curr][c]
      if curr in output:
        yield k, output[curr]
      k += 1

class Solution:
  def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
    trie, terminal = get_trie(forbidden)
    suffix, output = get_aho_corasick_automaton(trie, terminal)
    make_minimum_match_automaton(trie, terminal, output)
    
    max_valid = 0
    last_permissible = 0
    for terminal_index, pattern_index in get_minimum_matches(trie, suffix, output, word):
      initial_index = terminal_index - len(forbidden[pattern_index]) + 1
      max_valid = max(max_valid, terminal_index - last_permissible)
      last_permissible = max(initial_index+1, last_permissible)
    max_valid = max(max_valid, len(word)-last_permissible)
    return max_valid
201200