CF1070H. BerOS File Suggestion

H. BerOS File Suggestion
time limit per test3 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 files on hard drive and their names are f1,f2,…,fn. Any file name contains between 1 and 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”, “hosts”, “ops”, and “beros.18”, and the query is “os”, the number of matched files is 2 (two file names contain “os” as a substring) and suggested file name can be either “hosts” or “beros.18”.

Input
The first line of the input contains integer n (1≤n≤10000) — the total number of files.

The following n lines contain file names, one per line. The i-th line contains fi — the name of the i-th file. Each file name contains between 1 and 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) — the total number of queries.

The following q lines contain queries s1,s2,…,sq, one per line. Each sj has length between 1 and 8 characters, inclusive. It contains only lowercase Latin letters, digits and dot characters (’.’).

Output
Print q lines, one per query. The j-th line should contain the response on the j-th query — two values cj and tj, where

cj is the number of matched files for the j-th query,
tj is the name of any file matched by the j-th query. If there is no such file, print a single character ‘-’ instead. If there are multiple matched files, print any.
Example
inputCopy
4
test
contests
test.
.test
6
ts
.
st.
.test
contes.
st
outputCopy
1 contests
2 .test
1 test.
1 .test
0 -
4 test.

题目链接：CF1070H

题意：给你n个字符串，长度1-8，接下来q次查询，每次查询输入一个字符串s，问s是多少字符串的子串，输出个数和任意一个包含s子串的字符串

思路：可以看到每个字符串的长度才8，所以可以暴力的把字符串的所有子串全部搞出来，再用个map统计个数，然后用一个map存这个子串的完整字符串，就可以了

代码：

#include<bits/stdc++.h>
#define LL long long
#define Max 100005
const LL mod=1e9+7;
const LL LL_MAX=9223372036854775807;
using namespace std;
map<string,int>m,c[Max];
map<string,string>ans;
char a[9];
int main()
{
    int n;
    string s;
    scanf("%d",&n);
    for(int q=1;q<=n;q++){
        cin>>s;
        int len = s.length();
        for(int i=1;i<=len;i++){
            for(int j=0;j<len;j++){
                string t;
                int lens=0;
                if(j+i>len)
                    continue ;
                for(int k=j;k<j+i;k++)
                    a[lens++]=s[k];
                a[lens]='\0';
                t=a;
                if(!c[q].count(t)){//避免重复 如test，有两个t子串
                    c[q][t]=1;
                    m[t]++;
                    if(!ans.count(t))
                        ans[t]=s;
                   // cout<<t<<endl;
                  //  printf("%s\n",a);
                }
            }
        }
    }
    int q;
    scanf("%d",&q);
    while(q--)
    {
        string t;
        cin>>t;
        if(m.count(t)){
            cout<<m[t]<<" "<<ans[t]<<endl;
        }
        else{
            printf("0 -\n");
        }
    }
    return 0;
}