Untitled

 avatar
unknown
c_cpp
a year ago
973 B
6
Indexable
struct TrieNode{
    bool ends;
    int index;
    unordered_map<char, TrieNode*>child;
    TrieNode(): ends(false) {}
};
void insert(string s, int index){
    TrieNode* tmp = root;
    for(auto c: s){
        if(tmp->child.find(c) == tmp->child.end())
            tmp->child[c] = new TrieNode();
        tmp = tmp->child[c];
    }
    tmp->ends = true;
    tmp->index = index;
    return;
}
void query_suffix(string s, int index, vector<vector<int>> & ans){
    TrieNode *tmp = root;
    for (auto c : s){
        if (tmp->ends)
            ans.push_back({tmp->index, index});
        tmp = tmp->child[c];
    }
    return;
}
TrieNode* root = new TrieNode();
vector<vector<int>> problem4(vector<string> &word){
    int n = word.size();
    vector<vector<int>> ans;
    for(int i = 0; i < n; i++){
        reverse(word[i].begin(), word[i].end());
        insert(word[i], i);
        query_suffix(word[i], i, ans);
    }
    return ans;
}
Editor is loading...
Leave a Comment