题目描述

给定一个文本串 $\mathtt{T}$ 和一个模式串 $\mathtt{P}$，判断文本串 $\mathtt{T}$ 中是否存在模式串 $\mathtt{P}$。

输入格式

第一行，文本串 $\mathtt{T}$；

第二行，模式串 $\mathtt{P}$。

输出格式

如果 文本串 $\mathtt{T}$ 中存在模式串 $\mathtt{P}$，输出第一次匹配上的位置；否则，输出 $-1$。

注：这里所说的第一次匹配上的位置指的是最小的下标 $p$，其满足 $T_p$ 开始的长度为 $\mathtt{|P|}$ 的子串恰好等于模式串 $\mathtt{P}$（下标从 $1$ 开始，$\mathtt{|P|}$ 指的是模式串 $\mathtt{P}$ 的长度）。

样例

anjigaojizhongxue
ji

3

anjigaojizhongxue
angao

-1

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$\mathtt{|T|} \le 100, \mathtt{|P|} \le 10$
• 对于 $60\%$ 的数据，$\mathtt{|T|} \le 10000, \mathtt{|P|} \le 1000$
• 对于 $100\%$ 的数据，$1 \le \mathtt{|T|} \le 10^6, 1 \le \mathtt{|P|} \le 10^6$，字符串均由小写英文字母构成