0686. Repeated String Match

题目信息

题号:

0686

难度:

Medium

主题:

字符串重复、连续子串、最少重复次数

原题:

LeetCode 0686

重点:

只能把整个 a 首尾重复、b 必须作为连续子串出现、匹配可以跨越两个副本边界、无法出现时返回 -1

题目重述

给定两个非空小写字符串 a 和 b。把 a 重复若干次并首尾连接,寻找使 b 成为所得字符串连续子串的最少正重复次数。

b 可以从某个 a 副本的中间开始并跨越副本边界;不能重新排列或只重复 a 的一部分。若无论重复多少次都不能包含 b,返回 -1。a.length、b.length 位于 [1, 10^4]。

自建示例

目标跨越多个副本边界:

输入:a = "abc",b = "cabcab"
输出:3
解释:重复两次得到 "abcabc",仍不包含目标;重复三次得到 "abcabcabc",其中从字符 c 开始包含 "cabcab"。

目标含有源字符串不存在的字符:

输入:a = "ab",b = "ac"
输出:-1
解释:任意多个 "ab" 只会包含 a 和 b,不可能出现字符 c。