kotlin dp+kmp O(n*E) time and storage, both iterative and recursive
```\nclass Solution_iterative {\n    fun findGoodStrings(n: Int, s1: String, s2: String, evil: String): Int {\n        val base = 1_000_000_000 + 7\n        val
```\nclass Solution_iterative {\n    fun findGoodStrings(n: Int, s1: String, s2: String, evil: String): Int {\n        val base = 1_000_000_000 + 7\n        val E = evil.length\n        val dp = Array(n+1) { IntArray(E+1) { 0 } }\n\n        /**\n         * kmpArray: kmp pattern prefix array for evil: [i] is max length of prefix equals to suffix\n         * of substring evil.slice(0 .. i)\n         */\n        val kmpArray = IntArray(E+1) { 0 } // 1-indexed\n        var q = 0\n        for (i in 2 .. E) {\n            while (q > 0 && evil[i-1] != evil[q]) { // evil is 0-indexed\n                q = kmpArray[q]\n            }\n            if (evil[i-1] == evil[q]) {\n                q++\n            }\n            kmpArray[i] = q\n        }\n\n        fun containEvil(s: String): Boolean { // this is the classic KMP matcher\n            var res = false\n            var q = 0\n            for (i in 0 .. s.length-1) {\n                while (q > 0 && s[i] != evil[q]) {\n                    q = kmpArray[q]\n                }\n                if (s[i] == evil[q]) q++\n                if (q >= E) return true\n            }\n            return res\n        }\n\n        fun getJ(j: Int, c: Char): Int {\n            /**\n             * Given the prev string\'s suffix matches j-prefix evil, what is the largest match if adding char c to\n             * the end of the prev string. That is, it returns the max match of the suffix of string prev+c with evil.\n             * We don\'t need to know prev just j is enough.\n             */\n            var res = j\n            while (res > 0 && c != evil[res]) {\n                res = kmpArray[res]\n            }\n            if (c == evil[res]) {\n                res++\n            }\n            return res\n        }\n\n        fun precalcDP() {\n            /**\n             * dp[m][j] = number of strings of length m which does not have evil.substring(j) at the beginning and\n             *  does not contain evil as substring\n             */\n            for (m in 0 .. n) {\n                for (j in 0 .. E-1) {\n                    dp[m][j] = if (m == 0) {\n                        1\n                    } else {\n                        var res = 0\n                        for (c in \'a\' .. \'z\') {\n                            val newJ = getJ(j, c)\n                            res = (res + dp[m-1][newJ]) % base\n                        }\n                        res\n                    }\n                }\n            }\n        }\n\n        precalcDP()\n\n        fun goodStrings(upperBound: String): Int {\n            var jPath = 0\n            var res = 0\n            var pathTerminated = false\n            for (i in 0 .. n-1) {\n                if (i > 0) {\n                    jPath = getJ(jPath, upperBound[i-1])\n                }\n\n                if (jPath >= E) pathTerminated = true\n                if (pathTerminated) {\n                    //println("i: $i; pathTerminated: $pathTerminated")\n                    break\n                }\n                for (c in \'a\' .. upperBound[i]-1) { // exclude upper bound\n                    val j = getJ(jPath, c)\n                    val m = n - i\n                    res = (res + dp[m-1][j]) % base\n                }\n            }\n            if (!pathTerminated) { // reached here because we traversed all string upperBound\n                jPath = getJ(jPath, upperBound[n-1])\n                if (jPath < E) {\n                    res = (res + 1) % base\n                }\n            }\n            return res\n        }\n\n        val res1 = goodStrings(s1)\n        val s1ContainsEvil = containEvil(s1)\n        val res2 = goodStrings(s2)\n        //println("res1: $res1; res2: $res2; s1ContainsEvil: $s1ContainsEvil")\n        var res = (base + res2 - res1 + if (s1ContainsEvil) 0 else 1) % base // need to add base to avoid negative res\n\n        return res\n    }\n}\n\nclass Solution_recursive {\n    fun findGoodStrings(n: Int, s1: String, s2: String, evil: String): Int {\n        val base = 1_000_000_000 + 7\n        val E = evil.length\n        val dp = Array(n+1) { IntArray(E) { -1 } }\n\n        /**\n         * kmpArray: kmp pattern prefix array for evil: [i] is max length of prefix equals to suffix\n         * of substring evil.slice(0 .. i)\n         */\n        val kmpArray = IntArray(E+1) { 0 } // 1-indexed\n        var q = 0\n        for (i in 2 .. E) {\n            while (q > 0 && evil[i-1] != evil[q]) { // evil is 0-indexed\n                q = kmpArray[q]\n            }\n            if (evil[i-1] == evil[q]) {\n                q++\n            }\n            kmpArray[i] = q\n        }\n\n        fun containEvil(s: String): Boolean { // this is the classic KMP matcher\n            var res = false\n            var q = 0\n            for (i in 0 .. s.length-1) {\n                while (q > 0 && s[i] != evil[q]) {\n                    q = kmpArray[q]\n                }\n                if (s[i] == evil[q]) q++\n                if (q >= E) return true\n            }\n            return res\n        }\n\n        fun getJ(j: Int, c: Char): Int {\n            /**\n             * Given the prev string\'s suffix matches j-prefix evil, what is the largest match if adding char c to\n             * the end of the prev string. That is, it returns the max match of the suffix of string prev+c with evil.\n             * We don\'t need to know prev just j is enough.\n             */\n            var res = j\n            while (res > 0 && c != evil[res]) {\n                res = kmpArray[res]\n            }\n            if (c == evil[res]) {\n                res++\n            }\n            return res\n        }\n\n        fun recurse(m: Int, j: Int): Int {\n            /**\n             * return number of strings of length m which cannot have evil.substring(j) at the beginning and\n             *  cannot contain evil as substring\n             * Note: this fun does not depend on s1 or s2 so it can be used to precalc dp if so desired.\n             * x no need Note: if we want an iteractive algo to calc dp, for each m, we sort newJ(c), c in \'a\' .. \'z\'\n             */\n            if (j >= E) return 0\n            if (m <= 0) return 1\n            if (dp[m][j] != -1) return dp[m][j]\n\n            //// first letter\n            var res = 0\n            for (c in \'a\' .. \'z\') {\n                val newJ = getJ(j, c)\n                res = (res + recurse(m-1, newJ)) % base\n            }\n            dp[m][j] = res\n            return dp[m][j]\n        }\n\n        fun goodStrings(upperBound: String): Int {\n            var jPath = 0\n            var res = 0\n            var pathTerminated = false\n            for (i in 0 .. n-1) {\n                if (i > 0) {\n                    jPath = getJ(jPath, upperBound[i-1])\n                }\n\n                if (jPath >= E) pathTerminated = true\n                if (pathTerminated) {\n                    //println("i: $i; pathTerminated: $pathTerminated")\n                    break\n                }\n\n                for (c in \'a\' .. upperBound[i]-1) { // exclude upper bound\n                    val j = getJ(jPath, c)\n                    val m = n - i\n                    res = (res + recurse(m-1, j)) % base\n                }\n            }\n            if (!pathTerminated) { // reached here because we traversed all string upperBound\n                jPath = getJ(jPath, upperBound[n-1])\n                if (jPath < E) {\n                    res = (res + 1) % base\n                }\n            }\n            return res\n        }\n\n        val res1 = goodStrings(s1)\n        val s1ContainsEvil = containEvil(s1)\n        val res2 = goodStrings(s2)\n        //println("res1: $res1; res2: $res2; s1ContainsEvil: $s1ContainsEvil")\n        var res = (base + res2 - res1 + if (s1ContainsEvil) 0 else 1) % base // need to add base to avoid negative res\n\n        return res\n    }\n}
['Dynamic Programming', 'Recursion', 'Kotlin']