应该是这样的
2026-06-22 20:21:33
发布于:广东
1阅读
0回复
0点赞
给定基础串 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
#include<iostream>
#include<string>
using namespace std;
int main(){
string s,t;
cin>>s>>t;
bool vis[26]={0};
for(char c:s) vis[c-'a']=1;
for(char c:t)
if(!vis[c-'a']){cout<<-1;return 0;}
int cnt=0;
string cur=s;
while(1){
if(cur.find(t)!=string::npos){cout<<cnt;return 0;}
if(cur.size()>t.size()*2) break;
cur=cur+cur;
cnt++;
}
cout<<-1;
return 0;
}
这里空空如也







有帮助,赞一个