UVA 11988：Broken Keyboard (Beiju Text) - 鏈表模擬 Home/End 鍵

問題描述

輸入字符串包含字母、'[' (Home 鍵) 和 ']' (End 鍵)。Home 將光標移至行首，End 移至行末。輸出最終顯示的文本。長度 ≤ 100,000，多行輸入。

解法：靜態鏈表 / 數組模擬雙向鏈表

維護數組 next[i] 表示字符 i 後的字符索引。0 為虛擬頭節點。cur 為當前光標位置 (即最後插入字符的索引)。

• 初始 cur = 0 (行首)。
• 讀到 '['：cur = 0。
• 讀到 ']'：cur = last (last 為當前鏈表尾節點)。
• 普通字符 ch：分配新索引 idx，next[idx] = next[cur]，next[cur] = idx，cur = idx。若插在尾部則更新 last = idx。

最後從 next[0] 遍歷輸出。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXL = 100005;

int nxt[MAXL];
char val[MAXL];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line;
    while (getline(cin, line)) {
        int len = line.size();
        int cur = 0, last = 0, tot = 0;
        nxt[0] = 0;
        for (char ch : line) {
            if (ch == '[') cur = 0;
            else if (ch == ']') cur = last;
            else {
                val[++tot] = ch;
                nxt[tot] = nxt[cur];
                nxt[cur] = tot;
                cur = tot;
                if (nxt[cur] == 0) last = cur; // 插在尾部
            }
        }
        for (int i = nxt[0]; i; i = nxt[i]) cout << val[i];
        cout << '\n';
    }
    return 0;
}

關鍵點

• 靜態數組模擬鏈表，O(1) 插入，總 O(n)。
• last 維護尾節點，End 鍵 O(1) 定位。
• 虛擬頭節點 0 簡化邊界。

總結

經典「Broken Keyboard」問題，鏈表模擬光標移動與插入。靜態鏈表比 STL list 更快且內存友好，適合大數據量字符串處理。