原題及翻譯

Broken Keyboard (a.k.a. Beiju Text)
破碎的鍵盤(pán)（a.k.a. Beiju Text）
You’re typing a long text with a broken keyboard.
您正在鍵入一個(gè)破碎鍵盤(pán)的長(zhǎng)文本。
Well it’s not so badly broken.
好吧，它沒(méi)有那么糟糕。
The only problem with the keyboard is that sometimes the “home” key or the “end” key gets automatically pressed (internally).
鍵盤(pán)的唯一問(wèn)題是有時(shí)“自動(dòng)”鍵或“結(jié)束”鍵被自動(dòng)按下（內(nèi)部）。
You’re not aware of this issue, since you’re focusing on the text and did not even turn on the monitor!
你不知道這個(gè)問(wèn)題，因?yàn)槟銓?zhuān)注于文本，甚至沒(méi)有打開(kāi)監(jiān)控！
After you finished typing, you can see a text on the screen (if you turn on the monitor).
鍵入完成后，您可以在屏幕上看到文本（如果打開(kāi)顯示器）。
In Chinese, we can call it Beiju.
在中文里，我們可以稱(chēng)之為悲劇。
Your task is to find the Beiju text.
你的任務(wù)是找到悲劇文本。

Input

There are several test cases.
有幾個(gè)測(cè)試用例。
Each test case is a single line containing at least one and at most 100,000 letters, underscores and two special characters ‘[’ and ‘]’.
每個(gè)測(cè)試用例都是一行，包含至少一個(gè)，最多100,000個(gè)字符，下劃線和兩個(gè)特殊字符’[‘和’]’。
‘[’ means the “Home” key is pressed internally, and ‘]’ means the “End” key is pressed internally.
'[‘表示內(nèi)部按下“Home”鍵，’]表示內(nèi)部按下“End”鍵。
The input is terminated by end-of-file(EOF).
輸入由文件結(jié)束（EOF）終止。

Output

For each case, print the Beiju text on the screen.
對(duì)于每種情況，請(qǐng)?jiān)谄聊簧洗蛴”瘎∥谋尽?/p>

Sample Input

This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University

Sample Output

BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University

分析

最簡(jiǎn)單的想法便是使用數(shù)組來(lái)保存這段文本，然后用一個(gè)變量post保存“光標(biāo)位置”。這樣，輸入一個(gè)字符相當(dāng)于在數(shù)組中插入一個(gè)字符（需要先把后面的字符全部右移，給新字符騰出位置）。

但是，這樣的代碼會(huì)超時(shí)，因?yàn)檩斎胍粋€(gè)字符都可能會(huì)引起大量字符移動(dòng)。

解決方案是采用鏈表（linked list）。每輸入一個(gè)字符就把它存起來(lái)，設(shè)輸入字符串是s[1~n]，則可以用next[i]表示在當(dāng)前顯示屏中s[i]右邊的字符編號(hào)（即在s中的下標(biāo)）。

在數(shù)組中頻繁移動(dòng)元素是很低效的，如有可能，可以使用鏈表。

為了方便起見(jiàn)，假設(shè)字符串s的最前面還有一個(gè)虛擬的s[0]，則next[0]就可以表示顯示屏最左邊的字符。再用一個(gè)變量char表示光標(biāo)位置：即當(dāng)前光標(biāo)位于s[cur]的右邊。cur=0說(shuō)明光標(biāo)位于“虛擬字符”s[0]的右邊，即顯示屏的最左邊。

為了方便起見(jiàn)，常常在鏈表的第一個(gè)元素之前放一個(gè)虛擬結(jié)點(diǎn)。

為了移動(dòng)光標(biāo)，還需要一個(gè)變量last表示顯示屏的最后一個(gè)字符是s[last]。

代碼

#include <cstdio> #include <cstring> const int maxn=100000+5; int last,cur,next[maxn]; //光標(biāo)位于cur號(hào)字符的后面 char s[maxn];int main() {while(scanf("%s",s+1)==1){int n=strlen(s+1); //輸入保存在s[1],s[2]…中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; //更新“最后一個(gè)字符”編號(hào)cur=i; //移動(dòng)光標(biāo)}}for(int i=next[0];i!=0;i=next[i])printf("%c",s[i]);printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Broken Keyboard (a.k.a. Beiju Text)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。