当前位置：首页 > article >正文

【算法题】藏宝图

article 2025/9/11 20:03:39

牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t 是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。

输入描述:
每个输入包含一个测试用例。每个测试用例包含两行长度不超过 10 的不包含空格的可见 ASCII 字符串。

输出描述:
输出一行 “Yes” 或者 “No” 表示结果。

输入例子:
x.nowcoder.com
ooo

输出例子:
Yes

#include <iostream>
#include <numeric>
#include<algorithm>
#include <string>
#include<hash_map>
#include <set>
using namespace std;
//#define debug_void func(string s,string t)
{int last(-1);int tmp(0);for (auto i = 0; i < t.size();++i){tmp = find(s.begin()+(last+1), s.end(), t[i]) - s.begin();if (tmp == s.size()){cout << "No" << endl;return;}if (tmp>last){last = tmp;}else{cout << "No" << endl;return;}}cout << "Yes" << endl;
}int main()
{string s;string t;#ifdef debug_s = "abcd";t = "abcde";
#elsecin>>s;cin >> t;#endiffunc(s,t);return 0;
}

或者：

#include <iostream>
#include <numeric>
#include<algorithm>
#include <string>
#include<hash_map>
#include <set>
using namespace std;
//#define debug_void func(string s, string t)
{int i(0);int j(0);while ( i<s.size()&&j<t.size() ){if (s[i]==t[j]){++j;if (j == t.size()){cout << "Yes" << endl;return;}}++i;}cout << "No" << endl; 
}int main()
{string s;string t;#ifdef debug_s = "abcd";t = "abcde";
#elsecin >> s;cin >> t;#endiffunc(s, t);return 0;
}