题目描述

给你两个字符串 $haystack$ 和 $needle$ ，请你在 $haystack$ 字符串中找出 $needle$ 字符串的第一个匹配项的下标（下标从 0 开始）。如果 $needle$ 不是 $haystack$ 的一部分，则返回  $-1$ 。

输入格式

第一行一个字符串表示 $haystack$；

第二行一个字符串表示 $needle$。

输出格式

一行一个整数表示答案。

样例

示例 1：

sadbutsad
sad

0

解释： "sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

leetcode
leeto

-1

解释： "leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• $1 <= haystack.length, needle.length <= 10^6$
• $haystack$ 和 $needle$ 仅由小写英文字符组成

SOURCE

28. 找出字符串中第一个匹配项的下标