C++ DP (Detailed Explanation with Examples)
dp[i][j] is the number of substrings which are equal and end at s[i-1],t[j-1] respectively.\ndp1[i][j] is the number of substrings which end at s[i-1],t[j-1] an
dp[i][j] is the number of substrings which are equal and end at s[i-1],t[j-1] respectively.\ndp1[i][j] is the number of substrings which end at s[i-1],t[j-1] and differ by 1 char.\n\n**if s[i-1]==t[j-1]**, we can say that dp[i][j] is 1+dp[i-1][j-1] because all those substrings from dp[i-1][j-1] can be costructed here and the +1 corresponds to the substring which contains only the last character(s[i-1],t[j-1]). Here, dp1[i-1][j-1] will be dp1[i-1][j-1] because all those substrings from dp1[i-1][j-1] can be costructed here by appending the extra character(s[i-1],t[j-1]) which is same in both substrings.\n\n**Example:** \nAssume that dp[i-1][j-1] has substrings {"ab","ab"}. Lets say s[i-1]=t[j-1]=\'c\'. \nNow dp[i][j] will have {"abc","abc"},{"c","c"}.(which is one extra substring than dp[i-1][j-1]).\nAssume dp1[i-1][j-1] has subtrings {"ab","ae"}. Lets say s[i-1]=t[j-1]=\'c\'.\nNow dp1[i][j] will have {"abc","aec"} \n\n\n**if s[i-1]!=t[j-1]**, dp[i][j] will be zero because we can\'t construct equal substrings which end at s[i-1] and t[j-1] respectively. dp1[i][j] becomes 1+dp[i-1][j-1] because we can append this unequal chars(s[i-1],t[j-1]) to all those equal substrings of dp[i-1][j-1]. \n\n**Example:** \nAssume that dp[i-1][j-1] has substrings {"ab","ab"}. Lets say s[i-1]=\'c\' ans t[j-1]=\'d\'. \nNow dp[i][j] will have no equal substrings which end at s[i-1] and t[j-1].\nBut dp1[i][j] will have {"abc","abd"},{"c","d"}  \n\n```\nint countSubstrings(string s, string t) {\n        int n = s.length();\n        int m = t.length();\n        vector<vector<int>> dp(n+1,vector<int>(m+1));\n        vector<vector<int>> dp1(n+1,vector<int>(m+1));\n        int ans = 0;\n        \n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=m;j++)\n            {\n                if(s[i-1]==t[j-1])\n                {\n                    dp[i][j] = 1+dp[i-1][j-1];\n                    dp1[i][j] = dp1[i-1][j-1];\n                }\n                else\n                    dp1[i][j] = 1+dp[i-1][j-1];\n                ans += dp1[i][j];\n            }\n        }\n        return ans;\n    }\n```
[]