C語言判斷子序列：演算法實現與常見誤區分析

C語言判斷子序列：演算法實現與常見誤區分析

判斷序列 T 是否為序列 S 的子序列是經典的字串處理問題。本文提供完整 C 語言實現，並深入分析原始碼中存在的邏輯缺陷與修正方案。

問題定義

給定兩個序列 S 和 T，若 T 的所有元素按順序出現在 S 中（不要求連續），則稱 T 是 S 的子序列。例如 S="abcde"，T="ace" 是子序列，而 T="aec" 不是。

參考實作程式碼

#include <stdio.h>
#include <string.h>

int Subsequence(char s[], char t[]) {
    int m, n, i, j;
    n = strlen(s);  // S 的長度
    m = strlen(t);  // T 的長度
    
    if (m > n) return 0;  // T 比 S 長，不可能是子序列
    
    i = 0; j = 0;
    while (i < m && j < n) {
        if (t[i] == s[j]) {
            i++;  // T 當前字元匹配，移動到下一個
        }
        j++;  // S 永續向前掃描
    }
    
    // 正確判斷：若 T 所有字元都匹配完畢
    return (i == m) ? 1 : 0;
}

int main() {
    char s[30], t[30];
    int n, m = 1;
    
    printf("**************************************************\n");
    printf(" 子 序 列 判 定 算 法\n");
    printf("**************************************************\n\n");
    
    printf("請輸入測試組數（1～100）：");
    scanf("%d", &n);
    printf("\n");
    
    while (n--) {
        printf("請輸入第 %d 組主序列 S：", m);
        scanf("%s", s);
        printf("請輸入第 %d 組待判斷序列 T：", m);
        scanf("%s", t);
        
        if (Subsequence(s, t))
            printf("序列 T（%s）是序列 S（%s）的子序列。\n\n", t, s);
        else
            printf("序列 T（%s）不是序列 S（%s）的子序列。\n\n", t, s);
        m++;
    }
    return 0;
}

關鍵邏輯解析

正確的子序列判斷採用雙指針掃描法：

1. 指針 i 遍歷 T，指針 j 遍歷 S
2. 當 t[i] == s[j] 時，i++（T 推進）
3. j++ 無條件執行（S 持續掃描）
4. 最終若 i == m，說明 T 所有字元皆按序找到

原始碼錯誤分析

輸入內容中的原始實作存在兩個關鍵錯誤：

// 錯誤 1：匹配時雙雙遞增，導致 S 跳過字元
if(t[i]==s[j]) {
    i=i+1;
    j=j+1;  // 錯！S 不應在匹配時額外推進
}

// 錯誤 2：使用 strstr 判斷，這是檢查「子字串」而非「子序列」
if (strstr(s,t)!=NULL)
    return 1;

strstr 要求字元連續出現，僅能判斷子字串。例如 S="abcde"，T="ace" 會被誤判為非子序列。

複雜度分析

• 時間複雜度：O(n + m)，單次掃描
• 空間複雜度：O(1)，僅使用常數額外空間

測試驗證

掌握雙指針技巧，不僅能解決子序列問題，也是處理「最長公共子序列（LCS）」、「編輯距離」等動態規劃問題的基礎。