Tries || well explained
 Describe your first thoughts on how to solve this problem.  \nThe problem can also be solved using dp but i was not able to figure out the states, I saw the hi
<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can also be solved using dp but i was not able to figure out the states, I saw the hint, where I got the idea of using Tries.\n\nI did not find any solution in cpp using tries so I am posting this one. Please give it an upvote if you liked it.\n\nThe code may seem big but it\'s all standered stuff, be patient and go through this a couple of times, you will definately understand.\uD83D\uDE0A\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe approach is simple just put every substring of t in a Trie. Then for every substring of s (obviously, whose length is less than or equal to t) we can check how many substrings are there in the trie.\n\nTo do so we are just adding an extra parameter of terminatingCount which will store how any substrings will end at that particular character(node).\n\nThis can be understood as in the first sample example we can see that for the substring "a" in s we have two substrings "b" in t.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(t.length() * L * 26 + s.length() * L * 26)\nL=length of substring inserted in trie\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(t.length() * L * 26 + 2).\nL=length of substring inserted in trie\n\n# Code\n```\nclass TrieNode{\n    public:\n        TrieNode* children[26];\n        int terminatingCount;\n        TrieNode(){\n            for(int i=0;i<26;i++){\n                children[i]=NULL;\n            }\n            terminatingCount=0;\n        }\n};\nclass Solution {\nprivate:\n    // inserting the word in the trie.\n    void insertWord(TrieNode* root,string s){\n        if(s==""){\n            root->terminatingCount+=1;\n            return;\n        }\n        char x=s.front();\n        if(!((root->children)[x-\'a\'])){\n            TrieNode* newNode=new TrieNode();\n            root->children[x-\'a\']=newNode;\n        }\n        root=root->children[x-\'a\'];\n        insertWord(root,s.substr(1));\n    }\n    int check(TrieNode* root,string s,int cnt){\n        if(cnt==2){\n            // if we have replaced more than 1 character just return 0\n            return 0;\n        }\n        if(s==""){\n            if(cnt==1){\n                // reaching the end if we have only replaced 1 char then return the number of substrings ending at current node.\n                return root->terminatingCount;\n            }\n            // else return 0 as we have to replace only 1 character.\n            return 0;\n        }\n        char x=s.front();\n        int ans=0;\n        for(int i=0;i<26;i++){\n           if(root->children[i]){\n               if(i==x-\'a\'){\n                   // not replacing current character\n                   ans=ans+(check(root->children[i],s.substr(1),cnt));\n               }\n               else{\n                   // replacing current character\n                   ans=ans+(check(root->children[i],s.substr(1),cnt+1));\n               }\n           }\n        }\n        return ans;\n    }\npublic:\n    int countSubstrings(string s, string t) {\n        ios_base::sync_with_stdio(false);\n        TrieNode* root=new TrieNode();\n        int ans=0;\n\n        // inserting every substring of t in trie.\n        for(int i=0;i<t.length();i++){\n            string str="";\n            for(int j=i;j<t.length();j++){\n                str.push_back(t[j]);\n                insertWord(root,str);\n            }\n        }\n\n        // calculating ans\n        for(int i=0;i<s.length();i++){\n            string str="";\n            for(int j=i;j<s.length();j++){\n                str.push_back(s[j]);\n                if(str.length()<=t.length()){\n                    int res=check(root,str,0);\n                    ans=ans+res;\n                }\n            }\n        }\n        return ans;\n    }\n};\n```
['Trie', 'C++']