P11150 [THUWC 2018] 字胡串

来源：[https://www.gitlink.org.cn/thusaa/thuwc2018](https://www.gitlink.org.cn/thusaa/thuwc2018)。 2018 清华大学信息学冬季体验营（THUWC 2018）D1T3。$\texttt{2s,0.5G}$。 ---- 我希望你明白，优秀的出题人是懒得写题目背景的。但是优秀的题目也可能需要让选手了解一些基本定义， 例如以下这些内容， 而熟练的算法竞赛选手几乎可以无视。 对于一个字符串 $S$， 我们定义 $\left|S\right|$ 表示 $S$ 的长度。接着，我们定义 $S_i$ 表示 $S$ 中第 $i$ 个字符，$S_{L,R}$ 表示由 $S$ 中从左往右数，第 $L$ 个字符到第 $R$ 个字符依次连接形成的字符串。特别的，如果 $L>R$，或者 $L \notin \left[1,\left|S\right|\right]$，或者$R \notin \left[1,\left|S\right|\right]$，则我们可以认为 $S_{L,R}$ 为空串。 我们再定义两个字符串 $A$ 和 $B$ 的加法， $A+B$ 为将 $B$ 字符串整体连接在 $A$ 的最后一个字符后面得到的大字符串。 例如，我们可以认为 `aaaa` $+$ `bbbb` $=$ `aaaabbbb`。 我们不难发现，上述定义的加法满足结合律，但不满足交换律。 最后，我希望你还能明白，字典序是什么。 为了让你明白字典序是什么，你还需要明白前缀是什么。我们说一个字符串 $A$ 是另一个字符串 $B$ 的前缀，当且仅当存在一个整数 $len$，使得 $A$ 与 $B_{1,len}$ 是完全相同的字符串。 对于两个不同的字符串 $A$ 和 $B$，如果 $A$ 是 $B$ 的一个前缀，则我们认为在字典序下， $A < B$； 如果 $B$ 是 $A$ 的前缀，则我们认为在字典序下，$B < A$。 否则，我们总能找到一个最小的 $i$， 使得 $A_i \neq B_i$， 如果 $A_i < B_i$， 则我们认为在字典序下，$A < B$，否则 $B > A$。

现在给出一个长度为 $n$ 的字符串 $A$。 在此基础上，我会进行 $Q$ 次询问。 对于第 $i$（$1 \leq i \leq Q$）次的询问，我们会给出一个非空字符串 $B^{(i)}$， 并希望你找出一个最小的 $j$（$0 \leq j \leq n$）， 使得 $A_{1,j} + B^{(i)} + A_{j+1,n}$ 的字典序最小。 对于每个询问，你只需要输出你找到的这个 $j$ 即可。

从标准输入读入数据。 第一行有两个用空格隔开的整数 $n, Q$， 分别代表字符串 $A$ 的长度，以及询问次数。 第二行给出一个长度为 $n$ 的字符串，表示字符串 $A$。 第三行到第 $Q+2$ 行， 每行会给出一个非空字符串， 第 $i$ 行所给出的字符串表示 $B^{(i-2)}$。

输出到标准输出。 对于每个询问，请输出一行一个整数表示你所找到的最小的 $j$（$0 \leq j \leq n$）。

#### 子任务 | 测试点编号 | $n=$ | $\sum \left\lvert B^{(i)}\right\rvert\le$ | $Q\le$ | 其他约定 | | :--: | :--: | :--: | :--: | :--: | | $1\sim 3$ | $100$ | $100$ | $100$ | 无 | | $4\sim 8$ | $10^3$ | $10^3$ | $10^3$ | 无 | | $9\sim 10$ | $10^6$ | $10^6$ | $5\times 10^5$ | $\lvert B^{(i)}\rvert=1$ | | $11\sim 14$ | $3\times 10^5$ | $5\times 10^5$ | $3\times 10^5$ | 无 | | $15\sim 20$ | $10^6$ | $10^6$ | $5\times 10^5$ | 无 | 对于所有测试数据，$1 \leq n \leq 10^6$，$1 \leq Q \leq 5 \times 10^5$，$1 \leq \sum \limits _{i=1}^{Q} \left|B^{(i)}\right| \leq 10^6$，输入的字符串全部由**数字**组成。 此外，我们保证，对于所有测试数据， $\sum \limits _{i=1}^{Q} \left|B^{(i)}\right|$ 不会小于其在该测试点对应上界的 $\frac{1}{10}$。