C++ O(mn) using dp
use vector same[i][j] to record the number of same substrings that substr1 ends with s[i] and substr2 ends with t[j]\nuse vector diff[i][j] to record the numbse
use vector same[i][j] to record the number of same substrings that substr1 ends with s[i] and substr2 ends with t[j]\nuse vector diff[i][j] to record the numbser of substrings differ by one char that substr1 ends with s[i] and substr2 ends with t[j]\n\n```\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        vector<vector<int>> same(s.size(), vector<int>(t.size(), 0));\n        vector<vector<int>> diff(s.size(), vector<int>(t.size(), 0));\n        if (s[0] == t[0]) {\n            same[0][0] = 1;\n        } else {\n            diff[0][0] = 1;\n        }\n        int ret = diff[0][0];\n        for (int i = 1; i < s.size(); i++) {\n            if (s[i] == t[0]) same[i][0] = 1;\n            else diff[i][0] = 1;\n            ret += diff[i][0];\n        }\n        for (int j = 1; j < t.size(); j++) {\n            if (s[0] == t[j]) same[0][j] = 1;\n            else diff[0][j] = 1;\n            ret += diff[0][j];\n        }\n        for (int i = 1; i < s.size(); i++) {\n            for (int j = 1; j < t.size(); j++) {\n                if (s[i] == t[j]) {\n                    diff[i][j] = diff[i - 1][j - 1];\n                    same[i][j] = same[i - 1][j - 1] + 1;\n                } else {\n                    diff[i][j] = same[i - 1][j - 1] + 1;\n                }\n                ret += diff[i][j];\n            }\n        }\n        return ret;\n    }\n};\n```\nit is ok to replace 2D vectors with few variables, but lazy to do that.
[]