给定基础串 s,每次操作令 s=s+s(长度翻倍,操作次数 + 1);求最少操作次数,使得 t 是当前字符串的子串;永远无法满足输出 −1。关键观察 1:无解前置判定若 t 中存在某个字符,s 里完全没有,直接输出 −1;例:s=abc,t=ac,字符都有,但仍无解,只能先筛掉字符缺失的情况。关键观察 2:循环串本质不断拼接 s 等价于无限循环串 ssssssss⋯;只要 t 能出现在无限循环串中,就一定能在两段拼接 s+s
里找到;但我们题目要求每次只能翻倍,所以需要逐步翻倍直到长度足够覆盖 t。关键观察 3:循环终止条件设 len t 为 t 长度。如果当前字符串长度
> 2×len t
仍未找到子串,说明永远不可能出现,直接返回 −1
原因:更长的翻倍字符串只是重复原有循环,不会产生新的连续字符组合。
算法步骤
字符校验:统计 s 出现过的字母,遍历 t,有不存在字母直接输出 −1
初始化:当前串
cur=s,操作次数 cnt=0。
循环判断:若 cur 包含 t,输出 cnt 结束;
若
cur.size()>2×t.size(),无解输出 −1;
否则翻倍
cur=cur+cur,次数 cnt+1