UVA 11988 Broken Keyboard (Beiju Text) 解題詳解與鏈表實現

題目背景

這是一道經典的字符串處理問題，來自 UVA 11988。場景是：你在使用一個壞掉的鍵盤打字，Home 鍵和 End 鍵會被隨機觸發。'[' 代表 Home 鍵被按下（游標移至行首），']' 代表 End 鍵被按下（游標移至行首）。輸入包含字母、下劃線和這兩個特殊字符，長度最多 100,000，輸入文件不超過 5MB。任務是輸出最終顯示在屏幕上的文本（即 Beiju Text）。

核心思路：鏈表模擬游標操作

由於需要頻繁在行首、行尾或游標位置插入字符，使用數組模擬鏈表是最高效的做法。維護一個 next[] 數組，其中 next[i] 表示第 i 個字符後面的字符索引。用 cur 表示當前游標位置（即上一個插入字符的索引），last 表示當前鏈表的尾部索引。

• 遇到 '['：cur = 0（游標移至虛擬頭節點 0，下一次插入將在行首）
• 遇到 ']'：cur = last（游標移至尾部，下一次插入將在行尾）
• 遇到普通字符：在 cur 後插入新節點，更新 next 指針，並移動 cur 到新節點；若插入位置原本是尾部，同步更新 last。

關鍵代碼片段 (C++)

#include <cstdio>
#include <cstring>
const int MAXN = 100005;
char s[MAXN];
int nxt[MAXN];

int main() {
    while (scanf("%s", s + 1) == 1) {
        int len = strlen(s + 1);
        nxt[0] = 0;
        int cur = 0, last = 0;
        for (int i = 1; i <= len; ++i) {
            char c = s[i];
            if (c == '[') cur = 0;
            else if (c == ']') cur = last;
            else {
                nxt[i] = nxt[cur];
                nxt[cur] = i;
                if (cur == last) last = i;
                cur = i;
            }
        }
        for (int i = nxt[0]; i != 0; i = nxt[i]) putchar(s[i]);
        putchar('\n');
    }
    return 0;
}

複雜度分析

時間複雜度 O(n)，空間複雜度 O(n)，完美滿足題目限制。這種「數組模擬鏈表」技巧在處理大量插入/刪除操作時極為常用，值得熟練掌握。