POJ 1936 All in All：雙指針判斷子序列 O(n) 做法

題目大意

給定字符串 s 和 t，判斷 s 是否為 t 的子序列（即能從 t 中刪除若干字符得到 s）。多組測試，長度 ≤ 100,000。

雙指針掃描法

指針 i 遍歷 s，指針 j 遍歷 t：

• t[j] == s[i] → i++（匹配下一字符）
• j++ 始終執行
• 若 i == s.length() → Yes，否則 No

時間 O(|t|)，空間 O(1)，極其高效。

C++ 實現

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    while (cin >> s >> t) {
        int i = 0;
        for (char c : t) {
            if (i < (int)s.size() && c == s[i]) i++;
        }
        cout << (i == (int)s.size() ? "Yes" : "No") << '\n';
    }
    return 0;
}

樣例驗證

關鍵點

1. 子序列 ≠ 子串：不要求連續，只要求相對順序。
2. 大小寫敏感：直接比較字符碼值。
3. 多組輸入：while (cin >> s >> t) 直到 EOF。
4. 長度 100,000：O(n) 單遍掃描，ios::sync_with_stdio(false) 加速 IO。

擴展：輸出匹配位置

若需記錄 s 每字符在 t 中的位置，只需在匹配時 pos.push_back(j)。

總結

POJ 1936 是雙指針判斷子序列的標準模板題。核心洞見：貪心匹配最早可行位置 即可保證整體匹配。此技巧廣泛應用於字符串匹配、DNA 序列比對、版本控制差異檢測等場景。