立志用最少的代碼做最高效的表達

---

You’re typing a long text with a broken keyboard. Well it’s not so badly broken. The only problem
with the keyboard is that sometimes the “home” key or the “end” key gets automatically pressed
(internally).

You’re not aware of this issue, since you’re focusing on the text and did not even turn on the
monitor! After you finished typing, you can see a text on the screen (if you turn on the monitor).
In Chinese, we can call it Beiju. Your task is to find the Beiju text.

Input
There are several test cases. Each test case is a single line containing at least one and at most 100,000
letters, underscores and two special characters ‘[’ and ‘]’. ‘[’ means the “Home” key is pressed
internally, and ‘]’ means the “End” key is pressed internally. The input is terminated by end-of-file
(EOF).

Output
For each case, print the Beiju text on the screen.

Sample Input
This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University

Sample Output
BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University

---

分析

next數組作為存儲地址存在。

其中，next[0]可以理解為鏈表的頭結點。

核心代碼：

next[i] = next[cur]; //第一步 next[cur] = i; //第二步 cur = i; //第三步

這三行代碼可以理解為將一個節點插入的過程。

圖示：

如輸入： ab[cd]e
則：next[0] = 4; next[1] = 2; next[2] = 6; next[4] = 5; next[5] = 1; next[6] = -1;

最后根據next的地址輸出對應的s[i]即可。

---

附上劉汝佳先生的代碼

#include<stdio.h> #include<string.h> using namespace std;const int maxn = 100000+5; int last, cur, next[maxn]; //光標位于cur號字符的后面 char s[maxn];int main() {while(scanf("%s", s+1) == 1) {int n = strlen(s+1); //從1開始算last = cur = 0;next[0] = 0; for(int i = 1; i <= n; i++) {char ch = s[i];if(ch == '[') cur = 0;else if(ch==']') cur = last;else {next[i] = next[cur];next[cur] = i;if(cur == last) last = i; //更新“最后一個字符編號” cur = i; //移動光標 }}for(int i = next[0]; i != 0; i = next[i])printf("%c", s[i]);putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的【刘汝佳代码详解】例题6-4破损的键盘(Broken Keyboard,UVa 11988)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。