Little Shino and Substring Query

★★★★★

2 votes

Approved, Arrays, Data Structures, Medium, Segment Trees

Details

Submissions

Discussion

Editorial

Problem

Given N words and Q queries. Each query will have a string. You have to print two integers. Index of lexicographical smallest and largest string that contains the query string as substring. If there are multiple lexicographical smallest string, print the smallest index. If there are multiple lexicographical largest string, print the largest index. If there is no word that contains the query string as substring, print 1.

Note: Consider 0-indexing.

Input Format:
First line will contains two integers, N $(1 \le N \le 2 * 10^4)$ and Q $(1 \le Q \le 10^5)$ . Next line contains N space separated words, W $(1 \le |W| \le 10^5)$ . Next Q lines contain a string S $(1 \le |S| \le 10^5)$ each. Sum of lengths of all the words ( $sum(|W|)$ ) is less than or equal to $10^6$ . Sum of lengths of all the query strings ( $sum(|S|)$ ) is less than or equal to $2 * 10^7$ .

Output Format:
Print the index of lexicographical smallest and largest string that contains the string S as substring.

Time Limit: 3

Memory Limit: 256

Source Limit:

Explanation

Lexicographical order of the given words are:

$aab$
$abababc$
$abc$

$bc$ is a substring in $abababc$ and $abc$ . So lexicographical smallest and largest word that contains the $bc$ as substring are $abababc$ and $abc$ respectively.

$ab$ is a substring in all the words. So lexicographical smallest and largest word that contains the $ab$ as substring are $aab$ and $abc$ respectively.

a is a substring in all the words. So lexicographical smallest and largest word that contains the a as substring are $aab$ and $abc$ respectively.

d is a not substring in any of the given words. So the answer is 1.