UVA 10391 Compound Words

因为输入是字典序，所以拿着前一个词去匹配下一个词的开头，如果开头一样就去找结尾单词是否存在。用了 unordered_set以加快查找，不过其实还有优化的空间。

#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <unordered_set>

using namespace std;

vector<string> dict;
unordered_set<string> q_dict;
set<string> result;

int main() {
    string word, cur;
    while (cin >> word) {
        dict.push_back(word);
        q_dict.insert(word);
    }
    for (int i = 0; i < dict.size() - 1; i++) {
        word = dict[i];
        for (int j = i + 1; j < dict.size(); j++) {
            cur = dict[j];
            if (strncmp(word.c_str(), cur.c_str(), word.size()) != 0)
                break;
            string temp = cur.substr(word.size(), cur.size()-word.size());
            if (q_dict.count(temp) > 0)
                result.insert(cur);
        }
    }
    for (string s: result) {
        cout << s << endl;
    }
    return 0;
}