[CareerCup] 18.8 Search String 搜索字符串

class SuffixTreeNode {
public:
    unordered_map<char, SuffixTreeNode*> children;
    char value;
    vector<int> indexes;
    
    void insertString(string s, int idx) {
        indexes.push_back(idx);
        if (!s.empty()) {
            value = s[0];
            SuffixTreeNode *child;
            if (children.count(value)) {
                child = children[value];
            } else {
                child = new SuffixTreeNode();
                children[value] = child;
            }
            string remainder = s.substr(1);
            child->insertString(remainder, idx);
        }
    }
    
    vector<int> search(string s) {
        if (s.empty()) return indexes;
        char first = s[0];
        if (children.count(first)) {
            string remainder = s.substr(1);
            return children[first]->search(remainder);
        }
        return {};
    }
};

class SuffixTree {
public:
    SuffixTreeNode *root = new SuffixTreeNode();
    
    SuffixTree(string s) {
        for (int i = 0; i < s.size(); ++i) {
            string suffix = s.substr(i);
            root->insertString(suffix, i);
        }
    }
    
    vector<int> search(string s) {
        return root->search(s);
    }
};