Python 60ms, O(n^2), Trie + DFS
Construct a trie counting the number of substrings of t. It takes O(n^2).\nStarting at different characters in s with index i, use a dfs to sum up how many vali
Construct a trie counting the number of substrings of t. It takes O(n^2).\nStarting at different characters in s with index i, use a dfs to sum up how many valid substrings are there in s[i:]. Then sum up all i.\n\n\'\'\'\n\n\n    def countSubstrings(self, s: str, t: str) -> int:\n        Trie = lambda: defaultdict(Trie)\n        trie = Trie()\n        \n        for i in range(n):\n            node = trie\n            for x in t[i:]:\n                node = node[x]\n                if \'end\' in node:\n                    node[\'end\'] += 1\n                else:\n                    node[\'end\'] = 1\n        \n\n        \n        ans = 0\n        m = len(s)\n\n        def helper(i, node = trie, p = 1):\n\n            if i == m:\n                return node[\'end\']*(1 - p)\n            \n            ans =  node[\'end\']*(1 - p) if \'end\' in node else 0\n            for x in node:\n                if x != s[i] and p and x != \'end\':\n                    ans += helper(i + 1, node[x], 0)\n                elif x == s[i]:\n                    ans += helper(i + 1, node[x], p)\n\n            return ans\n        \n\n        for i in range(m):\n            ans += helper(i)\n        return ans\n\n\'\'\'
[]