Letters Shop

题意翻译

## 题目描述 字母商店的橱窗其实是一个由 $n$ 个小写字母组成的字符串 $s$！店如其名，这家店就是卖字母的。 字母商店卖的东西很奇怪，卖的方式更奇怪，它只从左往右卖，意思是说，你只能买这个字符串 $s$ 的前缀。 你有 $m$ 个好基友，第 $i$ 个的名字叫做 $t_i$。他们听说了这家店，都打算来买点字母，来拼出自己的名字，当然买来的字母是可以被打乱顺序或者干脆不用的。他们都想知道至少要买下几个字母才能拼出自己的名字。 举几个例子 - $s="arrayhead" , t_i="arya"$时，必须买下$"\underline{array}head"$ $5$个字母 - $s="arrayhead" , t_i="harry"$时，必须买下$"\underline{arrayh}ead"$ $6$个字母 - $s="arrayhead" , t_i="ray"$时，必须买下$"\underline{array}head"$ $5$个字母 - $s="arrayhead" , t_i="r"$时，必须买下$"\underline{ar}rayhead"$ $2$个字母 - $s="arrayhead" , t_i="areahydra"$时，必须买下$"\underline{arrayhead}"$ $9$个字母 字母商店的字母很齐全，所有的朋友肯定都能拼出自己的名字。 要注意的是，你的朋友们都只是在Doing [window shopping](https://baike.baidu.com/item/%E6%A9%B1%E7%AA%97%E8%B4%AD%E7%89%A9/9473660?fr=aladdin&fromid=8209896&fromtitle=Window+shopping)。他们只要你帮他们算出答案，并不会真正买下这些字母。 ## 输入输出格式 ### 输入格式： 第一行是一个整数 $n(1\leq n \leq 2 \times10^5)$ 表示橱窗 $s$ 的长度 第二行是字符串 $s$ 第三行一个整数 $m(1 \leq m \leq 5 \times10^4)$ 表示你的朋友个数 此后 $m$ 行 ,每一行有一个字符串 $t_i(1 \leq |t_i| \leq 2 \times 10^5)$ 你的朋友都很正常，所以他们名字总长度不会超过$2\times10^5$ ### 输出格式 共$m$行，第 $i$ 行对于第 $i$ 个朋友的询问输出他至少要买下几个字母才能拼出自己的名字。

题目描述

The letters shop showcase is a string $ s $ , consisting of $ n $ lowercase Latin letters. As the name tells, letters are sold in the shop. Letters are sold one by one from the leftmost to the rightmost. Any customer can only buy some prefix of letters from the string $ s $ . There are $ m $ friends, the $ i $ -th of them is named $ t_i $ . Each of them is planning to estimate the following value: how many letters (the length of the shortest prefix) would s/he need to buy if s/he wanted to construct her/his name of bought letters. The name can be constructed if each letter is presented in the equal or greater amount. - For example, for $ s $ ="arrayhead" and $ t_i $ ="arya" $ 5 $ letters have to be bought ("arrayhead"). - For example, for $ s $ ="arrayhead" and $ t_i $ ="harry" $ 6 $ letters have to be bought ("arrayhead"). - For example, for $ s $ ="arrayhead" and $ t_i $ ="ray" $ 5 $ letters have to be bought ("arrayhead"). - For example, for $ s $ ="arrayhead" and $ t_i $ ="r" $ 2 $ letters have to be bought ("arrayhead"). - For example, for $ s $ ="arrayhead" and $ t_i $ ="areahydra" all $ 9 $ letters have to be bought ("arrayhead"). It is guaranteed that every friend can construct her/his name using the letters from the string $ s $ . Note that the values for friends are independent, friends are only estimating them but not actually buying the letters.

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of showcase string $ s $ . The second line contains string $ s $ , consisting of exactly $ n $ lowercase Latin letters. The third line contains one integer $ m $ ( $ 1 \le m \le 5 \cdot 10^4 $ ) — the number of friends. The $ i $ -th of the next $ m $ lines contains $ t_i $ ( $ 1 \le |t_i| \le 2 \cdot 10^5 $ ) — the name of the $ i $ -th friend. It is guaranteed that $ \sum \limits_{i=1}^m |t_i| \le 2 \cdot 10^5 $ .

输出格式

For each friend print the length of the shortest prefix of letters from $ s $ s/he would need to buy to be able to construct her/his name of them. The name can be constructed if each letter is presented in the equal or greater amount. It is guaranteed that every friend can construct her/his name using the letters from the string $ s $ .

输入输出样例

输入样例 #1

9
arrayhead
5
arya
harry
ray
r
areahydra

输出样例 #1

5
6
5
2
9