C++ Trie Tree
\nstruct TrieNode {\n    TrieNode* children[26];\n    bool is_end;\n    int count;\n    \n    TrieNode() {\n        memset(children, 0, sizeof(children));\n    
```\nstruct TrieNode {\n    TrieNode* children[26];\n    bool is_end;\n    int count;\n    \n    TrieNode() {\n        memset(children, 0, sizeof(children));\n        is_end = false;\n        count = 0;\n    }\n};\n\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        TrieNode* root = new TrieNode();\n        int ret = 0;\n        \n        for(int i = 0; i < s.size(); i++) {\n            insert(root, s, i, s.size());\n        }\n        \n        for(int i = 0; i < t.size(); i++) {\n            search(root, t, i, t.size(), 0, ret);\n        }\n\n        return ret;\n    }\n\nprivate:\n    void insert(TrieNode* root, string word, int i, int len) {\n        root->is_end = true;\n        root->count += 1;\n        \n        if(i >= len) return;\n        \n        if(root->children[word[i]-\'a\'] == nullptr) {\n            root->children[word[i]-\'a\'] = new TrieNode();\n        }\n        \n        insert(root->children[word[i]-\'a\'], word, i+1, len);\n    }\n    \n    void search(TrieNode* root, string word, int i, int len, int mismatches, int& ret) {\n        if(mismatches > 1) return;\n        \n        if(1) {\n            if(mismatches == 1) {\n                ret += root->count;\n            }\n        }\n        \n        if(i >= len) return;\n        \n        for(int k = 0; k < 26; k++) {\n            if(root->children[k]) {\n                if(k == word[i]-\'a\') {\n                    search(root->children[k], word, i+1, len, mismatches, ret);\n                } else {\n                    search(root->children[k], word, i+1, len, mismatches+1, ret);\n                }\n            }\n        }\n    }\n};\n```
[]