C++ DP without KMP
this one is hard\n```\nclass Solution {\npublic:\n  int findGoodStrings(int n, string s1, string s2, string evil) {\n    init(evil);\n    auto noMoreThanS2 = le
this one is hard\n```\nclass Solution {\npublic:\n  int findGoodStrings(int n, string s1, string s2, string evil) {\n    init(evil);\n    auto noMoreThanS2 = lessThan(n, s2) + (s2.find(evil) == string::npos);\n    auto lessThanS1 = lessThan(n, s1);\n    auto res = (noMoreThanS2 + mod - lessThanS1) % mod;\n    return res;\n  }\n\n  long lessThan(int n, string s) {\n    auto pre = vector(m+1, pair{0LL, 0LL}), cur = pre;  //pair::first: num of curString < s; second: curString == s\n    pre[0] = pair{0, 1};\n    for (auto c : s) {\n      for (int i = 0; i < m; i++) {\n        for (int j = 0; j < 26; j++) {\n          int k = mat[i][j];\n          if (k == m) continue;\n          cur[k].first += pre[i].first;\n          if (\'a\' + j == c) cur[k].second += pre[i].second;\n          if (\'a\' + j < c)  cur[k].first += pre[i].second;\n        }\n      }\n      pre = move(cur);\n      for (auto &[x, y] : pre) {\n        x %= mod;\n        y %= mod;\n      }\n      cur = vector(m+1, pair{0LL, 0LL});\n    }\n    long res = 0;\n    for (auto &[x, y] : pre) res += x;\n    return res % mod;\n  }\n\n  void init(const string evil) {\n    m = evil.size();\n    mat = vector<vector<int>>(m + 1, vector<int>(26, 0));\n    for (int i = 0; i <= m; i++) {\n      auto prefix = evil.substr(0, i);\n      for (int k = 0; k < 26; k++) {\n        auto prefixK = prefix + char(\'a\' + k);\n        for (int j = 0; j < prefixK.size(); j++) {\n          auto suffix = prefixK.substr(j);\n          if (evil.find(suffix) == 0) {\n            mat[i][k] = suffix.size();\n            break;\n          }\n        }\n      }\n    }\n  }\n\n  int m = 0;\n  vector<vector<int>> mat; // i is the cur len match eval prefix, j is 0-25,  // mat[i][j] is the len match after add \'a\'+j\n  const long mod = 1e9 + 7;\n};
[]