POJ 1963 All in All：雙指針判斷子序列

問題描述

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

算法：雙指針線性掃描

• 指針 i 遍歷 s，指針 j 遍歷 t。
• 若 s[i] == t[j]，則 i++，j++；否則只 j++。
• 若最終 i == |s|，說明 s 所有字符按序匹配完畢 → Yes；否則 No。
• 時間 O(|t|)，空間 O(1)，極快。

優化細節

• 若 |s| > |t| 直接輸出 No。
• 用 scanf("%s%s", s, t) 讀取以空白分隔的字符串，自動處理換行。
• 字符串長度 100,000 需開 char s[100005]。

完整參考代碼

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100005;
char s[MAXN], t[MAXN];
int main(){
    while(scanf("%s%s", s, t) == 2){
        int ls = strlen(s), lt = strlen(t);
        if(ls > lt){ puts("No"); continue; }
        int i=0, j=0;
        while(i