<p>Given the strings <code>s1</code> and <code>s2</code> of size <code>n</code> and the string <code>evil</code>, return <em>the number of <strong>good</strong> strings</em>.</p>

<p>A <strong>good</strong> string has size <code>n</code>, it is alphabetically greater than or equal to <code>s1</code>, it is alphabetically smaller than or equal to <code>s2</code>, and it does not contain the string <code>evil</code> as a substring. Since the answer can be a huge number, return this <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

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

<pre>
<strong>Input:</strong> n = 2, s1 = &quot;aa&quot;, s2 = &quot;da&quot;, evil = &quot;b&quot;
<strong>Output:</strong> 51 
<strong>Explanation:</strong> There are 25 good strings starting with &#39;a&#39;: &quot;aa&quot;,&quot;ac&quot;,&quot;ad&quot;,...,&quot;az&quot;. Then there are 25 good strings starting with &#39;c&#39;: &quot;ca&quot;,&quot;cc&quot;,&quot;cd&quot;,...,&quot;cz&quot; and finally there is one good string starting with &#39;d&#39;: &quot;da&quot;.&nbsp;
</pre>

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

<pre>
<strong>Input:</strong> n = 8, s1 = &quot;leetcode&quot;, s2 = &quot;leetgoes&quot;, evil = &quot;leet&quot;
<strong>Output:</strong> 0 
<strong>Explanation:</strong> All strings greater than or equal to s1 and smaller than or equal to s2 start with the prefix &quot;leet&quot;, therefore, there is not any good string.
</pre>

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

<pre>
<strong>Input:</strong> n = 2, s1 = &quot;gx&quot;, s2 = &quot;gz&quot;, evil = &quot;x&quot;
<strong>Output:</strong> 2
</pre>

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

<ul>
	<li><code>s1.length == n</code></li>
	<li><code>s2.length == n</code></li>
	<li><code>s1 &lt;= s2</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>1 &lt;= evil.length &lt;= 50</code></li>
	<li>All strings consist of lowercase English letters.</li>
</ul>

class Solution {
 public:
  int findGoodStrings(int n, string s1, string s2, string evil) {
    vector<vector<vector<vector<int>>>> mem(
        n, vector<vector<vector<int>>>(
               evil.length(), vector<vector<int>>(2, vector<int>(2, -1))));
    // nextMatchedCount[i][j] := the number of next matched evil count, where
    // there're i matches with `evil` and the current letter is ('a' + j)
    vector<vector<int>> nextMatchedCount(evil.length(), vector<int>(26, -1));
    return count(s1, s2, evil, 0, 0, true, true, getLPS(evil), nextMatchedCount,
                 mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of good strings for s[i..n), where there're j matches
  // with `evil`, `isS1Prefix` indicates if the current letter is tightly bound
  // for `s1` and `isS2Prefix` indicates if the current letter is tightly bound
  // for `s2`.
  int count(const string& s1, const string& s2, const string& evil, int i,
            int matchedEvilCount, bool isS1Prefix, bool isS2Prefix,
            const vector<int>& evilLPS, vector<vector<int>>& nextMatchedCount,
            vector<vector<vector<vector<int>>>>& mem) {
    // s[0..i) contains `evil`, so don't consider any ongoing strings.
    if (matchedEvilCount == evil.length())
      return 0;
    // Run out of strings, so contribute one.
    if (i == s1.length())
      return 1;
    int& res = mem[i][matchedEvilCount][isS1Prefix][isS2Prefix];
    if (res != -1)
      return res;
    res = 0;
    const char minLetter = isS1Prefix ? s1[i] : 'a';
    const char maxLetter = isS2Prefix ? s2[i] : 'z';
    for (char c = minLetter; c <= maxLetter; ++c) {
      const int nextMatchedEvilCount = getNextMatchedEvilCount(
          nextMatchedCount, evil, matchedEvilCount, c, evilLPS);
      res += count(s1, s2, evil, i + 1, nextMatchedEvilCount,
                   isS1Prefix && c == s1[i], isS2Prefix && c == s2[i], evilLPS,
                   nextMatchedCount, mem);
      res %= kMod;
    }
    return res;
  }

  // Returns the lps array, where lps[i] is the length of the longest prefix of
  // pattern[0..i] which is also a suffix of this substring.
  vector<int> getLPS(const string& pattern) {
    vector<int> lps(pattern.length());
    for (int i = 1, j = 0; i < pattern.length(); ++i) {
      while (j > 0 && pattern[j] != pattern[i])
        j = lps[j - 1];
      if (pattern[i] == pattern[j])
        lps[i] = ++j;
    }
    return lps;
  }

  // j := the next index we're trying to match with `currLetter`
  int getNextMatchedEvilCount(vector<vector<int>>& nextMatchedCount,
                              const string& evil, int j, char currLetter,
                              const vector<int>& evilLPS) {
    int& res = nextMatchedCount[j][currLetter - 'a'];
    if (res != -1)
      return res;
    while (j > 0 && evil[j] != currLetter)
      j = evilLPS[j - 1];
    return res = (evil[j] == currLetter ? j + 1 : j);
  }
};
19600