A Trie Solution
Interesting that no one mentions a Trie solution. Time O(mm+nn)\n\n\nclass Solution {\n    class Node{\n        Node[] children;\n        int size;\n        pub
Interesting that no one mentions a Trie solution. Time O(m*m+n*n)\n\n```\nclass Solution {\n    class Node{\n        Node[] children;\n        int size;\n        public Node(){\n            children = new Node[26];\n            size = 0;\n        }\n    }\n    class Trie{\n        Node root;\n        public Trie(){\n            root = new Node();\n        }\n        public void insert(String s, int start){\n            Node current = root;\n            while(start<s.length()){\n                int index = s.charAt(start)-\'a\';\n                if(current.children[index]==null){\n                    current.children[index] = new Node();\n                }\n                current.children[index].size++;\n                current = current.children[index];\n                start++;\n            }\n        }\n        public int looseSearch(String s, int start){\n            int count = 0;\n            Node current = root;\n            for(int i=start; i<s.length(); i++){\n                char c = s.charAt(i);\n                if(current.children[c-\'a\']==null){\n                    //this is a miss match\n                    for(int j=0; j<26; j++){\n                        if(current.children[j]!=null){\n                            int temp = strictSearch(s, i+1, current.children[j]);\n                            count += temp;\n                        }\n                    }\n                    break;\n                }else{\n                    // make this a miss match\n                    for(int j=0; j<26; j++){\n                        if(j==c-\'a\' || current.children[j]==null){\n                            continue;\n                        }\n                        int temp = strictSearch(s, i+1, current.children[j]);\n                        count += temp;\n                    }\n                    // this is a match, proceed\n                    current = current.children[c-\'a\'];\n                }\n            }\n            return count;\n        }\n        \n        private int strictSearch(String s, int start, Node current){\n            int count = current.size;\n            while(start<s.length()){\n                if(current.children[s.charAt(start)-\'a\']!=null){\n                    current = current.children[s.charAt(start)-\'a\'];\n                    count += current.size;\n                    start++;\n                }else{\n                    break;\n                }\n            }\n            return count;\n        }\n    }\n    public int countSubstrings(String s, String t) {\n        Trie trie = new Trie();\n        for(int i=0; i<t.length(); i++){\n            trie.insert(t, i);\n        }\n        int count = 0;\n        for(int i=0; i<s.length(); i++){\n            count += trie.looseSearch(s, i);\n        }\n        return count;\n    }\n}\n```
[]