<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 mod  =  1e9+7 ; 
    string s1 ,s2 ,evil ; 
    vector<int> z_function(string &s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if(i < r) {
            z[i] = min(r - i, z[i - l]);
        }
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}
long dp[501][2][2][52] ;  
    int fun(int ind, int low, int high, int matched ) { 
        if(matched == evil.size()) return  0 ; 
        if(ind == s1.size()) return 1 ; 
        char cl = 'a' ; 
        char ch ='z' ; 
        if(low){
            cl =  s1[ind] ; 
        }
        if(high){
            ch = s2[ind] ; 
        }
        if(dp[ind][low][high][matched]!=-1) return dp[ind][low][high][matched] ; 
        long ans= 0  ; 
        for(char k =  cl ;k <=ch;k++){
            int nlow =  low ; 
            int nhigh =  high ; 
            if(k!=cl) nlow = 0 ; 
            if(k!=ch) nhigh = 0 ; 
            int nm =  matched; 
            if(evil[matched]== k) nm++;
            else{
                string temp = evil.substr(0,nm) ; 
                // prefix that is matched 
                temp+=  k;
                string pattern =  evil+ '&' +  temp ;
                auto z  =  z_function(pattern) ; 
                nm = 0 ; 
                for(int m =  evil.size()+1;m<pattern.size();m++){
                    if(z[m]+m-1== pattern.size()-1){
                        nm = z[m] ; 
                        break ; 
                    }
                }

            }
           ( ans+= fun(ind+1 , nlow, nhigh ,nm ))%=mod  ; 
        }
        return  dp[ind][low][high][matched]   =  ans ; 

    }
    int findGoodStrings(int n, string s1, string s2, string evil) {
        this->s1 = s1 ; 
        this->s2 =  s2  ; 
        this->evil =  evil ; 
        memset(dp,-1,sizeof dp) ; 
        return fun(0,1,1,0) ; 
    }
};
489900