题解：子序列判断问题（Subsequence）

一、题目分析

本题要求判断两个字符串中，第二个字符串s2或其反转是否为第一个字符串s1的子序列。子序列的定义是字符顺序保持相对不变，但不要求连续。因此，需要分别检查s2和s2的反转是否能在s1中找到对应的字符顺序。

二、核心思路

1. 正向检查（判断s2是否为s1的子序列）：
   遍历s1和s2，使用双指针法：

   • 指针j遍历s1，指针k遍历s2。
   • 当s1[j]等于s2[k]时，k后移一位，继续匹配下一个字符。
   • 若k成功遍历完s2，说明s2是s1的子序列。

2. 反向检查（判断s2的反转是否为s1的子序列）：
   对s2进行反转，得到rev_s2，再次使用双指针法检查rev_s2是否为s1的子序列。

   • 简化操作：直接在遍历s1时，从s2的末尾开始匹配，避免显式反转字符串。

三、代码解析

#include <iostream>
#include <string>
using namespace std;

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; ++i) {
        string s1, s2;
        cin >> s1 >> s2;
        bool found = false;

        // 检查s2是否为s1的子序列（正向）
        int k = 0; // 指向s2的当前字符
        for (char c : s1) {
            if (k < s2.size() && c == s2[k]) {
                k++;
            }
            if (k == s2.size()) {
                found = true;
                break;
            }
        }

        if (!found) {
            // 检查s2的反转是否为s1的子序列（反向）
            int r = s2.size() - 1; // 指向s2的末尾字符
            for (char c : s1) {
                if (r >= 0 && c == s2[r]) {
                    r--;
                }
                if (r == -1) {
                    found = true;
                    break;
                }
            }
        }

        cout << (found ? YES : NO) << endl;
    }
    return 0;
}

四、步骤详解

1. 输入处理：
   读取测试用例数T，依次处理每个测试用例，读取s1和s2。

2. 正向匹配：

   • 初始化指针k为0，遍历s1的每个字符c。
   • 若c与s2[k]相等，k后移一位。
   • 若k到达s2末尾（k == s2.size()），说明匹配成功，标记found为true并跳出循环。

3. 反向匹配（若正向失败）：

   • 初始化指针r为s2.size() - 1，遍历s1的每个字符c。
   • 若c与s2[r]相等，r前移一位。
   • 若r小于0（r == -1），说明s2的反转匹配成功，标记found为true并跳出循环。

4. 结果输出：
   根据found的值输出YES或NO。

五、关键点总结

• 双指针法的高效性：正向和反向匹配均使用双指针遍历s1和s2，时间复杂度为 ( O(len(s1)) )，对于长度不超过100的字符串，效率足够。
• 避免显式反转字符串：反向匹配时直接从s2的末尾开始匹配，减少内存操作和代码复杂度。
• 提前终止循环：一旦匹配成功，立即跳出循环，优化运行时间。

该解法通过两次线性遍历（正向和反向），简洁高效地解决了子序列判断问题，确保在题目给定的约束下快速正确地输出结果。