Multi String Search

• Time : O(size(small) * big.length + sum(all(small.length)))
• Space : O(max(small.length))

// kmp solution
vector<int> PI(string& s) {
    int n = s.length();
    vector<int> pi(n, 0);
    for(int i = 1, j = 0; i < n; i++) {
        while(j > 0 and s[i] != s[j]) j = pi[j - 1];
        if(s[i] == s[j])
            pi[i] = ++j;
    }

    return pi;
}

bool kmp(string& origin, string& target) {
    auto pi = PI(target);
    int n = origin.length();
    for(int i = 0, j = 0; i < n; i++) {
        while(j > 0 and origin[i] != target[j]) j = pi[j - 1];
        if(origin[i] == target[j])
            if(++j == target.length())
                return true;
    }
    return false;
}

vector<bool> multiStringSearch(string bigString, vector<string> smallStrings) {
    vector<bool> res;
    for(auto& s : smallStrings)
        res.push_back(kmp(bigString, s));
    return res;
}

• Time : O(max(small.length) * big.length + sum(all(small.length)))
• Space : O(sum(all(small.length)))

// trie solution
struct Trie {
    unordered_map<char, Trie*> next;
    string word = "";
    
    void insert(string& s, int p = 0) {
        if(p == s.length()) word = s;
        else {
            if(!next.count(s[p])) next[s[p]] = new Trie();
            next[s[p]]->insert(s, p +1);
        }
    }
    
    void query(string& s, int p, unordered_set<string>& us) {
        us.insert(word);
        if(p == s.length() or !next.count(s[p])) return;
        next[s[p]]->query(s, p + 1, us);
    }
};

vector<bool> multiStringSearch(string bigString, vector<string> smallStrings) {
    vector<bool> res;
    unordered_set<string> us;
    Trie* trie = new Trie();
    for(auto& s : smallStrings)
        trie->insert(s);
    for(int i = 0; i < bigString.length(); i++) {
        trie->query(bigString, i, us);
    }
    for(auto& s : smallStrings) {
        res.push_back(us.count(s));
    }
    return res;
}