Efficient JS solution - KMP + Digit DP with states
\n\nPro tip: Love lil Xi\xE8 \uD83D\uDC9C \u7231\u5C0F\u8C22 \uD83D\uDC9C\nNode: this is an advanced usage of KMP to quickly navigate the next matching substrin
![image.png](https://assets.leetcode.com/users/images/21b687e9-ddcd-4f69-b95f-a5fa4eb26bdb_1705573535.1926444.png)\n\nPro tip: Love lil Xi\xE8 \uD83D\uDC9C \u7231\u5C0F\u8C22 \uD83D\uDC9C\nNode: this is an advanced usage of KMP to quickly navigate the next matching substring.\n\n# Complexity\n- Let `e = evil.length`; `a = alphabet size = 26`\n- Time complexity: $$O(nea)$$\n- Space complexity: $$O(ea)$$\n\n# Code\n```js\n//#region KMP\nclass KMP {\n  /**\n   * Longest prefix suffix\n   * @param {string} s\n   * @param {number[]} [target]\n   * @returns {number[]}\n   */\n  static findLSP(s, target) {\n    let cur = 0;\n    let n = s.length;\n    const result = target ?? new Uint32Array(n);\n    result.fill(0, 0, n);\n\n    for (let i = 1; i < n; i++) {\n      while (cur && s[i] != s[cur]) cur = result[cur - 1];\n      if (s[i] == s[cur]) cur++;\n      else cur = 0;\n      result[i] = cur;\n    }\n\n    return result;\n  }\n}\n//#endregion\n\nlet MOD = 1000000007;\nlet lsp = new Uint8Array(51);\nlet links = Array.from({ length: 51 }, () => new Uint8Array(26));\nlet cur = new Uint32Array(51);\nlet pre = new Uint32Array(51);\n\n/**\n * @param {string} s\n * @param {number} el\n * @param {0 | 1} inclusive\n */\nfunction solve(s, el, inclusive) {\n  let n = s.length;\n\n  cur.fill(0, 0, n);\n  let c = 0;\n  let tightMatch = 0;\n  let tight = 1;\n\n  for (let i = 0; i < n; ++i) {\n    let tem = cur;\n    cur = pre;\n    pre = tem;\n\n    c = s.charCodeAt(i) - 97;\n    cur.fill(0);\n\n    if (tight) {\n      for (let nc = 0; nc < c; ++nc) {\n        ++cur[links[tightMatch][nc]];\n      }\n      tightMatch = links[tightMatch][c];\n      if (tightMatch == el) tight = 0;\n    }\n\n    for (let j = 0; j < el; ++j) {\n      for (let nc = 0; nc < 26; ++nc) {\n        cur[links[j][nc]] = (cur[links[j][nc]] + pre[j]) % MOD;\n      }\n    }\n  }\n\n  let res = inclusive * tight;\n  for (let i = 0; i < el; ++i) res = (res + cur[i]) % MOD;\n  return res;\n}\n\n/**\n * @param {number} n\n * @param {string} s1\n * @param {string} s2\n * @param {string} evil\n * @return {number}\n */\nvar findGoodStrings = function (n, s1, s2, evil) {\n  KMP.findLSP(evil, lsp);\n  let el = evil.length;\n\n  for (let i = 0; i < el; ++i) {\n    for (let c = 0; c < 26; ++c) {\n      links[i][c] = i ? links[lsp[i - 1]][c] : 0;\n    }\n    links[i][evil.charCodeAt(i) - 97] = i + 1;\n  }\n\n  return (solve(s2, el, 1) - solve(s1, el, 0) + MOD) % MOD;\n};\n```
['Dynamic Programming', 'String Matching', 'JavaScript']