C++ DP Solution
\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        int ans = 0;\n        int m = s.size(), n = t.size();\n\t\t//f: amount of su
```\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        int ans = 0;\n        int m = s.size(), n = t.size();\n\t\t//f: amount of substrings differ by 1 character till s[i]t[j]\n\t\t//i j begin from 1\n        vector<vector<int>> f(m + 1, vector<int>(n + 1));  \n\t\t//g:  amount of substrings that are the same till s[i]t[j]\n        auto g = f;\n        \n        for (int i = 1; i <= m; i++) {\n            for (int j = 1; j <= n; j++) {\n\t\t\t\t//if they are the same\n                if (s[i-1] == t[j-1]) {\n                    g[i][j] = g[i-1][j-1] + 1; //add g[i][j] by 1\n                    f[i][j] += f[i-1][j-1]; //f[i][j] wont change\n                }\n                else {\n                    f[i][j] += g[i-1][j-1] + 1; \n                    \n                }\n                ans += f[i][j];\n            }\n        }\n        return ans;\n    }\n};\n\n```
[]