HDU 5311 Hidden String：字符串匹配與 DFS 深搜優化

問題描述

給定字符串，判斷是否能通過刪除字符構成 "anniversary"，且刪除操作不超過 2 次（即保留字符分為最多 3 段）。

暴力三層循環解法

bool check(char *s) {
    int len = strlen(s);
    for (int i = 0; i < len; i++) if (s[i] == 'a')
        for (int j = i+1; j < len; j++) if (s[j] == 'n')
            for (int k = j+1; k < len; k++) if (s[k] == 'n')
                // ... 依次匹配 anniversary 11 個字符
                // 最後檢查剩餘字符是否能組成完整單詞
}

DFS 深搜優化解法

int dfs(int pos, int target_idx, int segments) {
    if (segments >= 3) return 0;  // 剪枝：超過 3 段直接失敗
    if (target_idx == 11) return 1;  // 匹配完成
    
    for (int i = pos; i < len; i++) {
        if (s[i] == target[target_idx]) {
            if (dfs(i+1, target_idx+1, segments + (i != pos))) return 1;
        }
    }
    return 0;
}

關鍵優化點

1. 段數剪枝：`segments >= 3` 直接返回，避免無效遞歸
2. 順序匹配：嚴格按 "anniversary" 字符順序搜索
3. 連續性判斷：`segments + (i != pos)` 判斷是否開始新段

複雜度對比

• 暴力三層循環：O(n³) 在 n=100 時約 10⁶ 操作
• DFS + 剪枝：實際運行更快，避免大量無效枚舉

比賽心得

「認真思考，敲一發，有信心過才是真正的 ACMer」——賽後發現多處邏輯漏洞，重構後通過最終測試。