K. 子串位置

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

翻译自 CSES-2104 题。

给定一个字符串和多个子串，找出每个子串第一次出现的位置（基于 $1$ 的索引）。如果子串没有出现，则输出 $-1$ 。

第一行包含一个长度为 $n$ 的字符串。

第二行包含一个整数 $k$ ，表示子串的数量。

接下来有 $k$ 行，每行包含一个子串。

字符串和子串中的字符都由小写字母 $a–z$ 组成。

对于每个子串，输出其在字符串中第一次出现的位置（ $1$ 索引）。如果该子串没有出现，则输出 $-1$ 。

aybabtu
3
bab
abc
a

3
-1
1

$1 \leq n \leq 10^5$ ；

$1 \leq k \leq 5 \times 10^5$ ；

所有子串的总长度最多为 $5 \times 10^5$ 。