Description

Submission

class Solution {
    int dp1[105][105];
    int dp2[105][105];
public:
    int countSubstrings(string s, string t) {
        int n = s.size();
        int m = t.size();

        s = "#" + s + "#";
        t = "#" + t + "#";

        // left to right
        for(int i = 1; i < n; ++i) {
            for(int j = 1; j < m; ++j) {
                if(s[i] == t[j]) dp1[i][j] = dp1[i-1][j-1]+1;
                else dp1[i][j] = 0;
            }
        }

        // right to left
        for(int i = n; i >= 1; --i) {
            for(int j = m; j >= 1; --j) {
                if(s[i] == t[j]) dp2[i][j] = dp2[i+1][j+1]+1;
                else dp2[i][j] = 0;
            }
        }

        int ret = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                if(s[i] != t[j]) {
                    ret += (dp1[i-1][j-1]+1) * (dp2[i+1][j+1]+1);
                }
            }
        }

        return ret;
    }
};