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

    const int MODULO = 1000000007;

    std::vector<int> compteKmpLpsTable(const std::string &pattern)
    {
        int m = pattern.size();
        std::vector<int> lps(m, 0);
        for (int i = 1, len = 0; i < m; ++i)
        {
            if (pattern[i] == pattern[len])
            {
                lps[i] = ++len;
            }
            else if (len > 0)
            {
                len = lps[len - 1];
                --i;
            }
        }
        return lps;
    }

    int dfs(int i,
            int j,
            bool m1,
            bool m2,
            const std::string &s1,
            const std::string &s2,
            const std::string &evil,
            std::vector<int> &kmp)
    {
        int m = evil.size();
        if (j == m)
        {
            return 0;
        }

        int n = s1.size();
        if (i == n)
        {
            return 1;
        }

        if (m_memo[i][j][m1][m2] != -1)
        {
            return m_memo[i][j][m1][m2];
        }

        char lower = m1 ? s1[i] : 'a';
        char upper = m2 ? s2[i] : 'z';
        
        int count = 0;
        for (char ch = lower; ch <= upper; ++ch)
        {
            int k = j;
            while (k > 0 && evil[k] != ch)
            {
                k = kmp[k - 1];
            }
            count = (count + dfs(i + 1, ch == evil[k] ? k + 1 : 0, m1 && ch == lower, m2 && ch == upper, s1, s2, evil, kmp)) % MODULO;
        }
        return m_memo[i][j][m1][m2] = count;
    }

    int findGoodStrings(int n,
                        const std::string &s1,
                        const std::string &s2,
                        const std::string &evil)
    {
        std::memset(m_memo, -1, 500 * 50 * 2 * 2 * sizeof(int));
        auto kmp = compteKmpLpsTable(evil);

        return dfs(0, 0, true, true, s1, s2, evil, kmp);
    }
    int m_memo[500][50][2][2];
};
8200