【UVA-10391】Compound Words【紫书】

【UVA-10391】Compound Words【紫书】

问题链接:https://vjudge.net/problem/UVA-10391

Solution:

两种思路,枚举所有拼接方式再根据set判重或枚举每个字符串的子串后set判重,前者复杂\(O(n^2)\),后者\(O(nm)\)。【其中m是字符串长度,这里忽略二者都需要的set判重的时间消耗】,结果是,前者会超时,后者可以ac。

后者的办法将每个字符串拆开成两个字符串,枚举所有拆法,判断两部分是否都在set中。使用string类下的assign()函数可以很方便的将子串摘出来。

另外,set判重除了可以使用find()函数,也可以用count()函数,对于set,count()的返回值只可能是0或1.

#include <iostream>
#include <vector>
#include <set>
#include <string>
using namespace std;

vector<string> data;
set<string> vis;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string str, l, r;
    while (cin >> str) vis.insert(str);
    for (auto &str : vis) {
        for (int i = 1; i < str.size() - 1; i++) {
            l.assign(str, 0, i);
            if (vis.find(l) != vis.end()) {
                r.assign(str, i, str.size() - i);
                if (vis.find(r) != vis.end()) {
                    cout << str << "\n";
                    break;
                }
            }
        }
    }
    return 0;
}