[codeforces1070H]BerOS File Suggestion

time limit per test : 3 seconds
memory limit per test : 256 megabytes

Polycarp is working on a new operating system called BerOS. He asks you to help with implementation of a file suggestion feature.

There are $n$n files on hard drive and their names are $f_1,f_2,…,f_n$f1​,f2​,…,fn​. Any file name contains between $1$1 and $8$8 characters, inclusive. All file names are unique.

The file suggestion feature handles queries, each represented by a string s
. For each query s it should count number of files containing s as a substring (i.e. some continuous segment of characters in a file name equals s) and suggest any such file name.
For example, if file names are $"read.me"$"read.me", $"hosts"$"hosts", $"ops"$"ops", and $"beros.18"$"beros.18", and the query is $"os"$"os", the number of matched files is $2$2 (two file names contain $"os"$"os" as a substring) and suggested file name can be either $"hosts"$"hosts" or $"beros.18"$"beros.18".

Input

The first line of the input contains integer $n(1≤n≤10000)$n(1≤n≤10000) — the total number of files.The following $n$n lines contain file names, one per line. The $i-th$i−th line contains $f_i$fi​ — the name of the $i-th$i−th file. Each file name contains between $1$1 and $8$8 characters, inclusive. File names contain only lowercase Latin letters, digits and dot characters (’.’). Any sequence of valid characters can be a file name (for example, in BerOS $".", ".."$".",".." and $"..."$"..." are valid file names). All file names are unique.

The following line contains integer $q(1≤q≤50000)$q(1≤q≤50000) — the total number of queries.

The following q lines contain queries $s_1,s_2,…,s_q$s1​,s2​,…,sq​, one per line. Each $s_j$sj​ has length between $1$1 and $8$8 characters, inclusive. It contains only lowercase Latin letters, digits and dot characters $('.')$(′.′).

Output

Print $q$q lines, one per query. The $j-th$j−th line should contain the response on the $j-th$j−th query — two values $c_j$cj​ and $t_j$tj​, where $c_j$cj​ is the number of matched files for the $j - th$j−th query, $t_j$tj​ is the name of any file matched by the $j -th$j−th query. If there is no such file, print a single character $'-'$′−′ instead. If there are multiple matched files, print any.

Input

4
test
contests
test.
.test
6
ts
.
st.
.test
contes.
st

Output

1 contests
2 .test
1 test.
1 .test
0 -
4 test.

题意：
给定n个字符串$f_1$f1​ 到 $f_n$fn​（长度为1~8），有$q$q个询问，每次询问一个字符串$s$s，问有多少$f_i$fi​满足$s$s是$f_i$fi​的子串，并且输出任意一个$f_i$fi​，如果不存在则输出$‘-’$‘−’

题解：
将所有$f_i$fi​的所有子串哈希，然后存入set，查询的时候只要直接询问就行了…不过cf机子特别快，你想用map<string,string>也可以

#include<bits/stdc++.h>
#define LiangJiaJun main
#define MOD 19991227
#define ULL unsigned long long
using namespace std;
int n;
map<ULL,int>pos,Hash;
set<ULL>prota;
set<ULL>::iterator it;
char s[10004][14];
int w33ha(){
    pos.clear();
    Hash.clear();
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]);
        int l=strlen(s[i]);
        prota.clear();
        for(int j=0;j<l;j++){
            ULL sum=0;
            for(int L=1;j+L-1<l;L++){
                sum=sum*256LL+(ULL)s[i][j+L-1];
                prota.insert(sum);
            }
        }
        for(it=prota.begin();it!=prota.end();it++){
            if(!Hash[(*it)])pos[(*it)]=i;
            Hash[(*it)]++;
        }
    }
    int q;
    scanf("%d",&q);
    while(q--){
        int l;
        ULL sum=0;
        char pt[14];
        scanf("%s",pt);
        l=strlen(pt);
        for(int i=0;i<l;i++)sum=sum*256LL+(ULL)pt[i];
        if(!Hash[sum]){
            puts("0 -");
        }
        else{
            printf("%d %s\n",Hash[sum],s[pos[sum]]);
        }
    }
    return 0;
}
int LiangJiaJun(){
    while(scanf("%d",&n)!=EOF)w33ha();
    return 0;
}