Find All Good Strings LeetCode solution in C++

1
class Solution {
2
 public:
3
  using ll = long long;
4
  int findGoodStrings(int n, string s1, string s2, string evil) {
5
    int M = 1e9 + 7;
6
    int m = evil.size();
7
    // kmp
8
    int f[m];
9
    f[0] = 0;
10
    for (int i = 1, j = 0; i < m; ++i) {
11
      while (j != 0 && evil[i] != evil[j]) {
12
        j = f[j - 1];
13
      }
14
      if (evil[i] == evil[j]) {
15
        ++j;
16
      }
17
      f[i] = j;
18
    }
19
    // next(i,c) jump function when matched i length and see c
20
    int next[m + 1][26];
21
    for (int i = 0; i <= m; ++i) {
22
      for (int j = 0; j < 26; ++j) {
23
        if (i < m && evil[i] == 'a' + j) {
24
          next[i][j] = i + 1;
25
        } else {
26
          next[i][j] = i == 0 ? 0 : next[f[i - 1]][j];
27
        }
28
      }
29
    }
30
    // dp(i,j,l1,l2) length i greater than s1, less than s2;
31
    // match j length of evil
32
    // l1 true means limited for s1, l2 true means limited for s2
33
    ll dp[n + 1][m + 1][2][2];
34
    memset(dp, 0, sizeof(dp));
35
    dp[0][0][1][1] = 1;
36
    for (int i = 0; i < n; ++i) {
37
      for (int j = 0; j < m; ++j) {
38
        for (int c = 0; c < 26; ++c) {
39
          int k = next[j][c];
40
          char ch = 'a' + c;
41
          dp[i + 1][k][0][0] += dp[i][j][0][0];
42
          if (dp[i][j][1][1]) {
43
            if (ch > s1[i] && ch < s2[i]) {
44
              dp[i + 1][k][0][0] += dp[i][j][1][1];
45
            } else if (ch == s1[i] && ch == s2[i]) {
46
              dp[i + 1][k][1][1] += dp[i][j][1][1];
47
            } else if (ch == s1[i]) {
48
              dp[i + 1][k][1][0] += dp[i][j][1][1];
49
            } else if (ch == s2[i]) {
50
              dp[i + 1][k][0][1] += dp[i][j][1][1];
51
            }
52
          }
53
          if (dp[i][j][1][0]) {
54
            if (ch > s1[i]) {
55
              dp[i + 1][k][0][0] += dp[i][j][1][0];
56
            } else if (ch == s1[i]) {
57
              dp[i + 1][k][1][0] += dp[i][j][1][0];
58
            }
59
          }
60
          if (dp[i][j][0][1]) {
61
            if (ch < s2[i]) {
62
              dp[i + 1][k][0][0] += dp[i][j][0][1];
63
            } else if (ch == s2[i]) {
64
              dp[i + 1][k][0][1] += dp[i][j][0][1];
65
            }
66
          }
67
          dp[i + 1][k][0][0] %= M;
68
        }
69
      }
70
    }
71
    ll ans = 0;
72
    for (int i = 0; i < m; ++i) {
73
      ans += dp[n][i][0][0] + dp[n][i][0][1] + dp[n][i][1][0];
74
      ans %= M;
75
    }
76
    return ans;
77
  }
78
};