POJ 3302 Subsequence 解题报告

一道水题，就是自己在输出时没有注意，将“YES”写成“Ｙes“，贡献了两次WA。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
/*判断str2是否str1的字串*/
bool isSubStr(string str1, string str2) {
    char c;
    string::size_type pos = 0;
    string::size_type ix = 0;
    for(; ix != str2.size(); ++ix) {
        c = str2[ix];
        pos = str1.find(c, pos);  //在主串str1中查找c,并返回c在str2中的位置
                                 //注意，根据题意要求，要从已被找到字符的下一个字符查到c在str2的第一次出现
        if(pos == string::npos) //若找不到，则返回string::npos，跳出for循环
            break;
        else
            str1.erase(pos, 1); //否则，在str2中除去c
    }
    if(ix == str2.size())
        return true;
    else
        return false;
}
int main()
{
    int n;
    cin >> n;
    string str1, str2;
    for(int i = 0; i < n; ++i) {
        cin >> str1 >> str2;
        /*下面的reverse函数会改变str2，故要先备份*/
        string str2_backup = str2;
        /*对str2进行倒置*/
        reverse(str2.begin(), str2.end());
        /*根据题目要求，str2或str2的倒置串是str1的字串均可*/
        if(isSubStr(str1, str2) || isSubStr(str1, str2_backup))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}