My Solution
\n/**\n * Time Complexity: O(n * n_evil * n_evil)\n * Space Complexity: O(n * n_evil)\n * where `n_evil` is the length of the string `evil`\n */\nclass Solution
```\n/**\n * Time Complexity: O(n * n_evil * n_evil)\n * Space Complexity: O(n * n_evil)\n * where `n_evil` is the length of the string `evil`\n */\nclass Solution {\n private:\n  static constexpr int letters = 26;\n  static constexpr char a = \'a\';\n  static constexpr int unmemorized = -1;\n  static constexpr int mod = 1000000007;\n  \n public:\n  int findGoodStrings(const int n,\n                      const string &s1,\n                      const string &s2,\n                      const string &evil) {\n    const int n_evil = static_cast<int>(evil.size());\n    int evil_next[n_evil + 1];\n    populate_evil_next(evil, evil_next);\n    vector<vector<int>> memo(n, vector<int>(n_evil, unmemorized));\n    const int item1 = dfs(s2, evil, evil_next, 0, 0, true, memo);\n    const int item2 = dfs(s1, evil, evil_next, 0, 0, true, memo);\n    const int item3 = is_good(s1, evil, evil_next) ? 1 : 0;\n    return ((mod + item1 - item2) % mod + item3) % mod;\n  }\n  \n private:\n  int dfs(const string &s,\n          const string &evil,\n          const int *evil_next,\n          const int index,\n          const int matched_evil_length,\n          const bool has_constraints,\n          vector<vector<int>> &memo) {\n    const int n_evil = static_cast<int>(evil.size());\n    if (matched_evil_length == n_evil) {\n      return 0;\n    }\n\n    const int n = static_cast<int>(s.size());\n    if (index == n) {\n      return 1;\n    }\n    \n    int ret = has_constraints ? unmemorized : memo[index][matched_evil_length];\n    if (ret != unmemorized) {\n      return ret;\n    }\n    \n    ret = 0;\n    const int letter = s[index] - a;\n    const int end_letter = has_constraints ? letter + 1 : letters;\n    for (int l = 0; l < end_letter; ++l) {\n      int j = matched_evil_length;\n      while (j != -1 && a + l != evil[j]) {\n        j = evil_next[j];\n      }\n      const int next_matched_evil_length = j + 1;\n      ret = (ret + dfs(s, evil, evil_next, index + 1, next_matched_evil_length, (has_constraints && l == letter), memo)) % mod;\n    }\n    \n    if (!has_constraints) {\n      memo[index][matched_evil_length] = ret;\n    }\n    return ret;\n  }\n  \n  bool is_good(const string &s, const string &evil, int *evil_next) {\n    const int n = static_cast<int>(s.size());\n    const int n_evil = static_cast<int>(evil.size());\n    int i = 0;\n    int j = 0;\n    while (i < n && j < n_evil) {\n      if (j == -1 || s[i] == evil[j]) {\n        ++i;\n        ++j;\n      } else {\n        j = evil_next[j];\n      }\n    }\n    return j != n_evil;\n  }\n  \n  void populate_evil_next(const string &evil, int *evil_next) {\n    const int n_evil = static_cast<int>(evil.size());\n    evil_next[0] = -1;\n    int i = 0;\n    int j = -1;\n    while (i < n_evil) {\n      if (j == -1 || evil[i] == evil[j]) {\n        ++i;\n        ++j;\n        evil_next[i] = j;\n      } else {\n        j = evil_next[j];\n      }\n    }\n  }\n};\n```
[]