Simple C# DP Solution with some comments. O(n^2)
\n    public class Solution\n    {\n        public int CountSubstrings(string s, string t)\n        {\n            checked\n            {\n                int r
```\n    public class Solution\n    {\n        public int CountSubstrings(string s, string t)\n        {\n            checked\n            {\n                int res = 0;\n\t\t\t\t//lcs = longest common substring\n                int[,] lcsLeft = new int[s.Length, t.Length];\n                int[,] lcsRight = new int[s.Length, t.Length];\n\n                for (int i = 0; i < s.Length; i++)\n                {\n                    for (int j = 0; j < t.Length; j++)\n                    {\n                        if (s[i] != t[j])\n                        {\n                            lcsLeft[i, j] = 0;\n                        }\n                        else\n                        {\n                            if (i > 0 && j > 0)\n                            {\n                                lcsLeft[i, j] = lcsLeft[i - 1, j - 1] + 1;\n                            }\n                            else\n                            {\n                                lcsLeft[i, j] = 1;\n                            }\n                        }\n                    }\n                }\n\n\n                for (int i = s.Length - 1; i >= 0; i--)\n                {\n                    for (int j = t.Length - 1; j >= 0; j--)\n                    {\n                        if (s[i] != t[j])\n                        {\n                            lcsRight[i, j] = 0;\n                        }\n                        else\n                        {\n                            if (i < s.Length - 1 && j < t.Length  - 1)\n                            {\n                                lcsRight[i, j] = lcsRight[i + 1, j + 1] + 1;\n                            }\n                            else\n                            {\n                                lcsRight[i, j] = 1;\n                            }\n                        }\n                    }\n                }\n\n\n                for (int i = 0; i < s.Length; i++)\n                {\n                    for (int j = 0; j < t.Length; j++)\n                    {\n                        if (s[i] != t[j]) //if characters mismatch we can make it equal and calculate how much substrings in s and t are equal\n                        {\n                            var left = 0;\n                            var right = 0;\n                            if (i > 0 && j > 0)\n                            {\n                                left = lcsLeft[i - 1, j - 1];\n                            }\n\n                            left++; //empty string can be on the left side\n                            if (i < s.Length - 1 && j < t.Length - 1)\n                            {\n                                right = lcsRight[i + 1, j + 1];\n                            }\n\n                            right++; // empty string can be on the right side\n\n                            res += left * right; //for any left prefix we can concatenate current char + any right postfix\n                        }\n                    }\n                }\n\n\n                return res;\n            }\n        }\n    }\n```
['Dynamic Programming']