W. 子串在哪里

    传统题 1000ms 256MiB

子串在哪里

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

给定两个仅由小写英文字母组成的字符串 ss 和 tt,请求出 tt 在 ss 中第一次出现的位置。

具体地,如果存在整数 ii(0≤i≤∣s∣−∣t∣0\le i\le |s|-|t|)使得 ss 中从下标 ii 的字符开始、连续 ∣t∣|t| 个字符按原顺序连起来恰好等于 tt(字符串的字符下标从 00 开始编号,第一个字符的下标是 00),则输出最小的这样的 ii;如果不存在这样的 ii,输出 -1。

匹配允许重叠:例如 s=aaaas=\texttt{aaaa}、t=aat=\texttt{aa} 时,tt 从下标 00 开始出现过,从下标 11 开始也出现过,从下标 22 开始还出现过,其中最小的是 00,所以答案是 00。

输入格式

输入共两行。

第一行一个字符串 ss(1≤∣s∣≤10 0001\le |s|\le 10\,000,仅由小写英文字母 a 到 z 组成,不含空格等任何空白字符)。

第二行一个字符串 tt(1≤∣t∣≤∣s∣1\le |t|\le |s|,仅由小写英文字母 a 到 z 组成,不含空格等任何空白字符)。

两行都非空,行末的换行符不属于字符串内容。

输出格式

输出一行一个整数,表示 tt 在 ss 中第一次出现的起始下标(下标从 00 开始);若 tt 不是 ss 的子串,则输出 -1。

对每组输入,符合要求的答案唯一确定,因此本题只有一个正确答案,请不要输出除这个整数以外的任何内容。

数据范围

  • 1≤∣s∣≤10 0001\le |s|\le 10\,000。
  • 1≤∣t∣≤∣s∣1\le |t|\le |s|。
  • ss 与 tt 的每个字符都是小写英文字母 a 到 z。

样例

样例 1

ababcabc
abc
2

t=abct=\texttt{abc} 在 ss 中出现了两次:一次从下标 22 开始(abc),一次从下标 55 开始(abc)。第一次出现的下标是 22,所以输出 22。

样例 2

aaaa
aab
-1

ss 中所有长度为 33 的连续片段只有 aaa,它不等于 aab,所以 tt 不是 ss 的子串,输出 -1。

样例 3

aaaaa
aaa
0

t=aaat=\texttt{aaa} 从下标 00、11、22 开始都能匹配(这些出现互相重叠),其中最小的是 00,所以输出 00。

说明

  • 下标从 00 开始编号,第一个字符的下标是 00,最后一个字符的下标是 ∣s∣−1|s|-1。
  • 匹配允许重叠,要找的是第一次出现的位置,而不是最后一次,也不是出现的次数。
  • 请注意 tt 与 ss 完全相等、tt 是 ss 的前缀、tt 只出现在 ss 的末尾、tt 根本不出现这几种情况。

2026级SYUCT-ACM新生第四次训练

未参加
状态
已结束
规则
XCPC
题目
40
开始于
2026-10-30 18:30
结束于
2026-11-16 10:30
持续时间
400 小时
主持人
参赛人数
62