풀이
주어지는 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;
}