Simple Java solution using Trie for slow learners like myself (2ms)
The idea is to create all possible substrings of s and store it in trie.\n\nThen iterate all possible substrings of t and try finding a match in the trie.\n\n\n
The idea is to create all possible substrings of s and store it in trie.\n\nThen iterate all possible substrings of t and try finding a match in the trie.\n\n```\nclass Solution {\n    public int countSubstrings(String s, String t) {\n        s = s == null ? "" : s;\n        t = t == null ? "" : t;\n        if (s.length() > t.length())\n            return countSubstrings(t, s);\n        \n        Node root = buildTrie(s);\n        int count = 0;\n        char[] arr = t.toCharArray();\n        \n        for (int i = 0; i < t.length(); i++) \n            count += findMatch(root, arr, i, false);\n        \n        return count;\n    }\n    \n    private int findMatch(Node root, char[] arr, int pos, boolean used) {\n        if (root == null || pos == arr.length)\n            return 0;\n        char c = arr[pos];\n        int total = 0;\n        if (used) {\n            if (root.nodes[c - \'a\'] == null)\n                return 0;\n            return root.nodes[c - \'a\'].count + findMatch(root.nodes[c - \'a\'], arr, pos + 1, true);\n        }\n        \n        for (char a = \'a\'; a <= \'z\'; a++) {\n            if (root.nodes[a - \'a\'] == null)\n                continue;\n            if (a == c)\n                total += findMatch(root.nodes[a - \'a\'], arr, pos + 1, false);\n            else\n                total += (findMatch(root.nodes[a - \'a\'], arr, pos + 1, true) + root.nodes[a - \'a\'].count);\n        }\n        \n        return total;\n    }\n    \n    private static final class Node {\n        final Node[] nodes = new Node[26];\n        int count = 0;\n    }\n    \n    private Node buildTrie(String s) {\n        Node root = new Node();\n        char[] arr = s.toCharArray();\n        for (int i = 0; i < s.length(); i++)\n            insert(root, arr, i);\n        return root;\n    }\n    \n    private void insert(Node root, char[] arr, int start) {\n        int len = arr.length, size = 0;\n        Node cur = root;\n        \n        while (start < len) {\n            char c = arr[start++];\n            if (cur.nodes[c - \'a\'] == null)\n                cur.nodes[c - \'a\'] = new Node();    \n            cur = cur.nodes[c - \'a\'];\n            cur.count++;\n        }\n    }\n}\n```
[]