应该是这样的
2026-06-22 20:21:33
发布于:广东
20阅读
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;
}
全部评论 1
#include<iostream>
#include<string>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
bool vis[26] = {0};for(int i = 0 ;i < s.size();i++){ vis[s[i] - 'a'] = 1; } for(int i = 0 ;i < t.size();i++){ if (!vis[t[i] - 'a']) { cout << -1; return 0; } } int cnt = 0; string cur = s; while (1) { if (cur.find(t) != -1) { cout << cnt; return 0; } if (cur.size() > t.size() * 2){ break; } cur = cur + cur; cnt++; } cout << -1; return 0;}
zheyangzigengjiandan1周前 来自 新疆
0











有帮助,赞一个