Dew It | No KMP, O(m*n) | 8ms (very fast Java sol)
BASIC IDEA\nIt helps to IMAGINE a completely filled trie of depth n (DO NOT construct this). The left boundary of the trie is that path of leaf s1 and the right
**BASIC IDEA**\nIt helps to IMAGINE a completely filled trie of depth ```n``` (DO NOT construct this). The left boundary of the trie is that path of leaf ```s1``` and the right boundary is same for ```s2``` - what we need is the **count of leaves between these two boundaries** such that ```evil``` is not a part of the path.\nThe dynamic programming part is where we add levels to this tree (trie) one by one. What we indirectly store is the number of ```good``` strings we have seen so far (a new good string is a child of an existing good string)\n\n* From 0 to n-1, we add characters one by one to ```s1```, ```s2``` and all strings between s1 and s2\n* ```store``` is a ```[3][m]``` sized 2D array where 0th row represents s1, 2nd row represents s2 and 1st row represents every string lexicographically between s1 and s2\n* We store counts of certain *categories* of strings in ```store```. These categories are basically: **strings suffixed with r sized prefix of** ```evil```  (*where r ranges from 0 to m-1*)\n* An example to understand what ```store``` is: after ```k``` additions (loop from step 1), essentially ```store[1][5]``` represents the count of strings in between ```s1``` and ```s2``` of **size** ```k``` such that they **end** with the **first** ```5``` characters of ```evil```\n* If we have all ```store[i][j]``` for the kth step, the problem reduces to finding ```store[i][j]``` for the (k+1)th step and keep doing it until ```n```.\nIn the end return ```(store[0][0] + store[1][0] + store[2][0])```\n* Let\'s generate the "next" ```store[][]``` in a temporary matrix called ```next``` (which is of the same size ```[3][m]```).\n* The most crucial part is the following relationship:\n```store[0]``` feeds ```next[0]```\n```store[2]``` feeds ```next[2]```\n```store[0]```, ```store[1]``` and ```store[2]``` feed ```next[1]```\n\nI think the rest is self explanatory if you read the code\n(Why create ```suffix```? What is the exact relationship between ```store``` and ```next```? and so on)\n\n**CODE**\n```\nclass Solution {\n    final int MOD = 1000000007;\n    final boolean PRINT = false;\n    \n    boolean[] suffix;\n    char[] a, b, e;\n    int n, m;\n    \n    // Why the redundant parameter n in the first place??\n    public int findGoodStrings(int whatTheHell, String s1, String s2, String evil) {\n        a = s1.toCharArray(); b = s2.toCharArray(); e = evil.toCharArray();\n        n = a.length; m = e.length;\n        \n        // First task is to find the longest "common" prefix for s1 and s2\n        int index = 0;\n        while(index < n && a[index] == b[index]) ++index;\n        if(index < n && b[index] < a[index]) return 0; // if s2 < s1, return 0\n        \n        /*\n        Suffix is a boolean array of size m where suffix[i] is true if\n        prefix of size (i+1) is same as suffix of size (i+1)\n        */\n        initSuffix();\n        \n        // Analysis starts at \'start\'\n        int start = 0;\n        if(index >= m) {\n            if(s1.substring(0, index).indexOf(evil) != -1) return 0;\n            else start = index - m + 1;\n        }\n        // We use indices from start to index to initialize store\n        long[][] store = initStore(start, index);\n        \n        // Saving the starting point <- logic within while loop different the very first time\n        start = index;\n        while(index < n) {\n            long[][] next = new long[3][m];\n            \n            /*\n            if(start == index)\n                feed store[0] to next[1] with new char in (a[index], b[index])\n            else\n                feed store[0] to next[1] with new char in (a[index], \'z\']\n                feed store[2] to next[1] with new char in [\'a\', b[index])\n                feed store[1] to next[1] with new char in [\'a\', \'z\']\n            */\n            char low = a[index], hi = \'z\';\n            if(index == start) {\n                hi = b[index];\n                --hi;\n            }\n            ++low;\n            dewIt(store[0], next[1], low, hi);\n            \n            char c;\n            long sum;\n            if(index > start) {\n                hi = b[index]; --hi;\n                dewIt(store[2], next[1], \'a\', hi);\n                dewIt(store[1], next[1], \'a\', \'z\');\n            }\n            \n            dewIt(store[0], next[0], a[index], a[index]);\n            dewIt(store[2], next[2], b[index], b[index]);\n            \n            store = next;\n            ++index;\n            if(PRINT) System.out.println(Arrays.deepToString(store));\n        }\n        return (int) ((store[0][0] + store[1][0] + store[2][0])%MOD);\n    }\n    \n    private void dewIt(long[] source, long[] dest, char low, char hi) {\n        for(char c=low; c<=hi; ++c) feed(source, dest, c);\n        // dest[0] is not handled in the feed function\n        // we decrease iff last char of evil exists within our range\n        long dec = ((e[m-1] >= low && e[m-1] <= hi)?source[m-1]:0);\n        dest[0] = (dest[0] + (hi-low+1)*source[0] - dec)%MOD;\n        if(dest[0] < 0) dest[0] += MOD;\n    }\n    \n    private void feed(long[] source, long[] dest, char c) {\n        // If c is the last char in evil, we may discard some strings\n        boolean minus = (c == e[m-1]);\n        for(int i=0; i<m-1; ++i) {\n            // Discard only if suffix[i] is also true\n            long remove = ((minus && suffix[i]) ? source[m-1]:0);\n            if(c == e[i]) {\n                dest[i+1] += (source[i] - remove);\n                dest[i+1] %= MOD;\n                if(dest[i+1] < 0) dest[i+1] += MOD;\n            }\n        }\n    }\n    \n    private long[][] initStore(int start, int index) {\n        long[][] store = new long[3][m];\n        for(int i=start; i<index; ++i) {\n            int x = i, y = 0;\n            boolean nah = false;\n            while(x < index) {\n                if(a[x] != e[y]) {\n                    nah = true;\n                    break;\n                }\n                ++x; ++y;\n            }\n            if(!nah) {\n                int l = index - i;\n                store[0][l] = 1;\n                store[2][l] = 1;\n            }\n        }\n        store[0][0] = 1; store[2][0] = 1;\n        if(PRINT) System.out.println(Arrays.deepToString(store));\n        return store;\n    }\n    \n    private void initSuffix() {\n        suffix = new boolean[m];\n        for(int i=0; i<m; ++i) {\n            int x = 0, y = m-1-i;\n            boolean nah = false;\n            while(y < m) {\n                if(e[x] != e[y]) {\n                    nah = true;\n                    break;\n                }\n                ++x; ++y;\n            }\n            suffix[i] = !nah;\n        }\n        if(PRINT) System.out.println(Arrays.toString(suffix));\n    }\n}\n```
['Java']