链接: https://cses.fi/problemset/task/2104

板块: String Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个字符串和若干模式串，找出每个模式串在字符串中第一次出现的位置（从 1 开始编号）。

输入

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

下一行包含一个整数 $k$：模式串的个数。最后有 $k$ 行描述这些模式串。

字符串和模式串均由 a–z 组成。

输出

输出每个模式串第一次出现的位置（如果完全未出现则输出 $-1$）。

数据范围

$1 \le n \le 10^5$ $1 \le k \le 5 \cdot 10^5$ 模式串的总长度至多为 $5 \cdot 10^5$

样例输入

aybabtu
3
bab
abc
a

样例输出

3
-1
1