【解題】All in All

ACM Volume CIII 10340 - All in All


The Problem

You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way. Because of pending patent issues we will not discuss in detail how the strings are generated and inserted into the original message. To validate your method, however, it is necessary to write a program that checks if the message is really encoded in the final string.

Given two strings s and t, you have to decide whether s is a subsequence of t, i.e. if you can remove characters from t such that the concatenation of the remaining characters is s.


The Input

The input contains several testcases. Each is specified by two strings s, t of alphanumeric ASCII characters separated by whitespace. Input is terminated by EOF.


The Output

For each test case output, if s is a subsequence of t.


Sample Input

sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter


Sample Output

Yes
No
Yes
No


解題思考

　　這一題主要是給兩個字串 s 跟 t，問你 t 有沒有可能在移去某些字元後，能夠得到 s。

　　既然如此，我們可以直接利用 string::find() 函式，依序從 t 中去找 s 的每一個字元。假如都找得到，就輸出 "Yes"，否則輸出 "No"。這樣就完成了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    string s, t;
    while (cin >> s >> t)
    {
        int pos = -1;
        bool ok = true;
        for (int i = 0; i < s.size(); i++)
        {
            // 搜尋 s 的元素是否依序存在 t 中
            if ((pos = t.find(s[i], pos + 1)) == string::npos)
            {
                ok = false;
                break;
            }
        }

        cout << (ok ? "Yes" : "No") << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}