[Codeforces 1070H] BerOS File Suggestion

[Codeforces 1070H] BerOS File Suggestion - 1600

문제 설명 : 

처음에 n개의 파일이름(문자열)이 주어진다. 그 다음 q개의 쿼리가 들어오는데, 각 쿼리는 substring을 제시하여 n개의 파일 중에서 해당 substring 포함하는 파일은 총 몇 개인지와 존재한다면 아무 파일이름을 출력하면 된다.

풀이 : 

정말 고민을 많이 했던 문제이다. 일단 n이 1만, q가 5만이기 때문에 각 쿼리마다 모든 n을 살펴보는 것은 시간이 초과된다( O(n*q) ). 따라서 반드시 전처리과정을 거친 뒤에야 쿼리를 받을 때 빠르게 답을 출력하는 형태가 될 것이라고 짐작했다. 실제로 솔루션은 한 문자열에서 나올 수 있는 모든 substring의 경우의 수를 map에다 저장해서 카운트 해놓고, 나중에 쿼리가 들어올 때마다 map에 저장된 값을 출력하면 되는 것이다. 이 풀이가 가능한 이유는 파일이름(문자열)의 최대 길이가 8글자이기 때문이다. 따라서 한 문자열에서 나올 수 있는 substring에 최대 경우의 수는 (1+2+3..+8)=28가지이다. n은 1만이므로 28만개의 공간이 사용되는 것이다.

주의할 점 : 

한 문자열 내에서 동일한 substring이 여러번 등장할 수 있으므로(ex. aabaa) 일단 set에 substring을 넣어 중복을 제거한 뒤에 map에 넣어야지 중복 카운트를 피할 수 있다. 

배운 점 : 

string객체위 함수에 concat의 기능을 수행하는 push_back연산이 있다는 것을 깨달았다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
/****************************Contest Template******************************/
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
typedef long long ll;
typedef unsigned long long ull;
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
/****************************Contest Template******************************/
// const int SIZE=
 
map<string,string> mss;
map<string,int> msi;
 
int main(){
    int n,q;    scanf("%d",&n);
 
    while(n--){
        string str;    cin>>str;
        set <string> ss;
 
        for(int i=0 ; i<str.size() ; i++){
            string substr;
            
            for(int j=i ; j<str.size() ; j++){
                substr.push_back(str[j]);
                ss.insert(substr);
            }
        }
        
        for(auto here:ss){
            msi[here]++;
            mss[here]=str;
        }
 
    }
 
    scanf("%d",&q);
    while(q--){
        string find;    cin>>find;
 
        if(msi[find]!=0){
            printf("%d ",msi[find]);
            cout<<mss[find]<<'\n';
        }
        else{
            printf("0 -\n");
        }
    }
    
 
    return 0;
}