c++ bottom up DP
First compute kmp failure function.\nThen use it to compute next function, where next(i, c) means that when match i length and see character c, jump to length n
First compute kmp failure function.\nThen use it to compute next function, where next(i, c) means that when match i length and see character c, jump to length next(i, c).\nFinally compute dp(i, j, l1, l2), i is current length, j is current match length of evil, l1 is true if current matching is same as s1, l2 is true if current matching is same as s2.\n# Code\n```\nclass Solution {\npublic:\n    using ll = long long;\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n      int M = 1e9+7;\n      int m = evil.size();\n      // kmp\n      int f[m];\n      f[0] = 0;\n      for (int i = 1, j = 0; i < m; ++i) {\n        while (j != 0 && evil[i] != evil[j]) {\n          j = f[j-1];\n        }\n        if (evil[i] == evil[j]) {\n          ++j;\n        }\n        f[i] = j;\n      }\n      // next(i,c) jump function when matched i length and see c\n      int next[m+1][26];\n      for (int i = 0; i <= m; ++i) {\n        for (int j = 0; j < 26; ++j) {\n          if (i < m && evil[i] == \'a\'+j) {\n            next[i][j] = i+1;\n          } else {\n            next[i][j] = i == 0? 0: next[f[i-1]][j];\n          }\n        }\n      }\n      // dp(i,j,l1,l2) length i greater than s1, less than s2;\n      // match j length of evil\n      // l1 true means limited for s1, l2 true means limited for s2\n      ll dp[n+1][m+1][2][2];\n      memset(dp, 0, sizeof(dp));\n      dp[0][0][1][1] = 1;\n      for (int i = 0; i < n; ++i) {\n        for (int j = 0; j < m; ++j) {\n          for (int c = 0; c < 26; ++c) {\n            int k = next[j][c];\n            char ch = \'a\'+c;\n            dp[i+1][k][0][0] += dp[i][j][0][0];\n            if (dp[i][j][1][1]) {\n              if (ch > s1[i] && ch < s2[i]) {\n                dp[i+1][k][0][0] += dp[i][j][1][1];\n              } else if (ch == s1[i] && ch == s2[i]) {\n                dp[i+1][k][1][1] += dp[i][j][1][1];\n              } else if (ch == s1[i]) {\n                dp[i+1][k][1][0] += dp[i][j][1][1];\n              } else if (ch == s2[i]) {\n                dp[i+1][k][0][1] += dp[i][j][1][1];\n              }\n            }\n            if (dp[i][j][1][0]) {\n              if (ch > s1[i]) {\n                dp[i+1][k][0][0] += dp[i][j][1][0];\n              } else if (ch == s1[i]) {\n                dp[i+1][k][1][0] += dp[i][j][1][0];\n              }\n            }\n            if (dp[i][j][0][1]) {\n              if (ch < s2[i]) {\n                dp[i+1][k][0][0] += dp[i][j][0][1];\n              } else if (ch == s2[i]) {\n                dp[i+1][k][0][1] += dp[i][j][0][1];\n              }\n            }\n            dp[i+1][k][0][0] %= M;\n          }\n        }\n      }\n      ll ans = 0;\n      for (int i = 0; i < m; ++i) {\n        ans += dp[n][i][0][0] + dp[n][i][0][1] + dp[n][i][1][0];\n        ans %= M;\n      }\n      return ans;\n    }\n};\n```
['C++']