1070H : BerOS File Suggestion

풀이

주어지는 string의 길이가 엄청 짧다.

모든 substring을 다 잘라서 자료구조에 넣어주자.

그럼 쉽게 구현할 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <string>
using namespace std;

int n, q;
string a[10001];
map<string, pair<int, int> > m;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n;
    for (int k = 0; k < n; k++) {
        string str;
        cin >> str;
        a[k] = str;
        set<string> s;
        for (int i = 0; i < str.length(); i++) {
            for (int j = 1; j <= str.length(); j++) {
                if (i+j > str.length()) continue;
                string tmp = str.substr(i, j);
                s.insert(tmp);
            }
        }
        for (auto it : s) {
            m[it].first++;
            m[it].second = k;
        }
    }
    cin >> q;
    while (q--) {
        string str;
        cin >> str;
        if (m.count(str) > 0) {
            cout << m[str].first << " " << a[m[str].second];
        }
        else cout << "0 -";
        cout << "\n";
    }

    return 0;
}
wookje.kwon's profile image

wookje.kwon

2018-11-14 12:59

Read more posts by this author