1. Problem Description:

Given n strings f1, f2,..., fn, these strings are different from each other. The following q queries are given. Among them, the ith query is given a string si. Your task is:
Calculate the number of strings containing si as a substring in the n strings f1 ∼ fn;
From the n strings f1 ∼ fn, select any string containing si as the substring output;

Input format

The first line contains the integer n, and the next N lines, where line i contains the string fi. The next line contains the integer q. Next, line q, where line i contains the string si, and all FI and si contain only lowercase letters, numbers, and

Output format

There are q lines in total, and the i-th line outputs the answer to the i-th query. First, output the number of strings containing si as a substring in the n strings f1 ∼ fn, and then output any string containing si as a substring from the n strings f1 ∼ fn. If such a string is not unique, you can output any reasonable string. If such a string does not exist, you can output -.

Data range

The first three test points meet 1 ≤ n, q ≤ 20;
All test points meet the requirements of 1 ≤ n ≤ 10000, 1 ≤ q ≤ 50000, 1 ≤|fi |, |si | ≤ 8;

Input example:

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

Output example:

1 contests
2 .test
1 test.
1 .test
0 -
4 test.
Source: https://www.acwing.com/problem/content/description/4401/

2. thought analysis:

From the analysis of the topic, we can know that the length of each FI and Si meets the following requirements: 1 < = |fi|, |si| ≤ 8, so the length of the string is very short, so the number of substrings is relatively small. For a string with length of 8, the corresponding number of substrings is (1 + 8) * 8 / 2 = 36, a total of 10000 f strings, so the total number of substrings is 36 w. we can open a hash table to store these substrings, The time complexity is about 360000 * 8 = 2880000, which can be passed; Since it is necessary to output the number of strings of fi containing the substring Si and the fi containing the corresponding Si, it is necessary to open at least two hash tables, in which the hash table count is used to record the number of occurrences of the substring Si in FI, the hash table mp is used to record the string fi corresponding to the substring Si, and the substring s corresponding to each fi may be repeated, so it is necessary to open a hash table s to remove duplication, Stores all non repeating substrings in fi.

3. the code is as follows:

python:

class Solution:
    def process(self):
        n = int(input())
        count, mp = dict(), dict()
        i = 0
        while n > 0:
            s = input()
            # S for weight removal
            S = set()
            for i in range(len(s)):
                # s1 splice all substrings
                s1 = ""
                for j in range(i, len(s)):
                    s1 += s[j]
                    S.add(s1)
            # Enumerate all substrings in s
            for x in S:
                if x not in count:
                    count[x] = 1
                else:
                    count[x] += 1
                # mp is used to record one of the strings corresponding to a string
                mp[x] = s
            n -= 1
        m = int(input())
        for i in range(m):
            s = input()
            if s in mp:
                print(count[s], mp[s])
            else:
                print(0, "-")


if __name__ == "__main__":
    Solution().process()

go:

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

func run(r io.Reader, w io.Writer) {
	// Use bufio Newreader() optimizes the efficiency of input and output data
	in := bufio.NewReader(r)
	out := bufio.NewWriter(w)
    // Write cached output to standard output
	defer out.Flush()
	var (
		n, m int
		s    string
	)
	fmt.Fscan(in, &n)
	count := make(map[string]int)
	// mp record string corresponding to substring
	mp := make(map[string]string)
	for k := 0; k < n; k++ {
		fmt.Fscan(in, &s)
		// S for weight removal
		S := make(map[string]int)
		// Splice all substrings in s
		for i := 0; i < len(s); i++ {
			s1 := ""
			for j := i; j < len(s); j++ {
				s1 += string(s[j])
				S[s1] = 1
			}
		}
		// Traversal hash table
		for key := range S {
			count[key] += 1
			mp[key] = s
		}
	}
	// m queries
	fmt.Fscan(in, &m)
	for i := 0; i < m; i++ {
		fmt.Fscan(in, &s)
		v, flag := mp[s]
		if flag {
			fmt.Fprintln(out, count[s], v)
		} else {
			fmt.Fprintln(out, 0, "-")
		}
	}
}

func main() {
	run(os.Stdin, os.Stdout)
}