OpenJudge | 全在其中

Mryan2005

总时间限制: 1000ms 内存限制: 65536kB

描述

你设计了一个新的加密技术，可以用一种聪明的方式在一个字符串的字符间插入随机的字符串从而对信息进行编码。由于专利问题，我们将不会详细讨论如何在原有信息中产生和插入字符串。不过，为了验证你的方法，有必要写一个程序来验证原来的信息是否全在最后的字符串之中。

给定两个字符串s和t，你需要判断s是否是t的“子列”。也就是说，如果你去掉t中的某些字符，剩下字符将连接而成为s。

输入

输入包括多个测试样例。每一个都是由空格分隔的由字母数字ASCII字符组成的两个特定的字符串s和t。s和t的长度不超过100000。

输出

对于每个测试样例，如果s是t的“子列”，则输出”Yes”，否则输出”No”

样例输入

sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter

样例输出

Yes
No
Yes
No

来源

Ulm Local 2002

分析

这是一个典型的查找问题，查找字符，不是字符串字串，并且不是每次都从t开始往后找，而是从找到的地方继续往后找。
此时就可以想到一个类似于映射的数据结构了，这个映射结构可以实现重复，所以不可能是Map<char, char>，而是vector<pair<char, char>>。
最后就是要判定s是否是t的“子列”：这里可以考虑判断vector的长度是否等于字符串s的。

Code

C++ STL

#include <bits/stdc++.h>

using namespace std;

int main() {
	string s, t;
	while(cin >> s >> t)  {
		vector<pair<char, char>> v;
		long long unsigned int begin = 0;
		bool canntFound = 1;
		for(long long unsigned int i = 0; i < s.size(); i++) {
			for(long long unsigned int j = begin; j < t.size(); j++) {
				if(t[j] == s[i]) {
					pair<char, char> pa = {s[i], t[j]};
					v.insert(v.end(), pa);
					begin = j+1; 
					break;
				}
			}
		}
		if(v.size() == s.size()) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}