4.悲劇文本

問題描述：
你有一個破損的鍵盤燃箭。鍵盤上所有的鍵都可以正常工作，但有時候Home鍵或者End鍵會自動按下。你并不知道鍵盤存在這一問題，而是專心打稿子音念，甚至連顯示器都沒打開。當你打開顯示器后躏敢，展現(xiàn)在你面前的是一段悲劇文本闷愤。你的任務是在打開顯示器之前計算出這段悲劇文本。
輸入包含多組數(shù)據(jù)件余。每組數(shù)據(jù)占一行讥脐，包含不超過100000個字母、下劃線啼器、字符“【”或者“】”旬渠。其中字符“【”表示Home鍵，“】”表示End鍵端壳。輸入結束標志為文件結束符（EOF）告丢。輸入文件不超過5MB。對于每組數(shù)據(jù)损谦，輸出一行岖免，即屏幕上的悲劇文本岳颇。

樣例輸入：

This_is_a_[Beiju]_text

樣例輸出：

BeijuThis_is_a_text
分析：
如果使用數(shù)組來存儲該輸入文本，當遇到''["(home)鍵時繼續(xù)輸入文本會產(chǎn)生大量的位移操作觅捆，浪費大量的時間這里我們可以采用鏈表赦役。這個問題中我采用的是靜態(tài)鏈表。解題思路：想象在編輯文檔時候的情形栅炒，用一個鏈表表示輸入的字符掂摔，有一個可任意移動的光標，可以在光標的位置插入字符赢赊，我們在程序中要存儲光標的位置乙漓，最后一個字符的位置。

#include<cstdio>
#include<cstring>
const int maxn = 100000 + 5;
int last, cur, next[maxn];
char s[maxn];
//遍歷字符串释移，如果是"["光標cur=0;
//如果是']'光標cur = last;
//如果是字母則進行插入操作：
//  當前字符的下一個字符編號為光標所在位字符的下一個字符編號;
//  光標所在位置的字符的下一個字符編號為當前字符編號叭披；
//  更新光標的位置
//  如果光標的位置為最后一個字符last的位置那么更新最后一個字符的位置
int main() {
    //輸入字符串;
    while(scanf("%s",s+1) == 1){
        int n = strlen(s+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;//模擬鏈表的插入
                    cur = i;//更新光標的位置
                    if(cur == last) last = i;//更新最后一個字符的位置
                }
        }
        //打印
        for(int i = next[0];i != 0; i = next[i])
            printf("%c",s[i]);
        printf("\n");
    }
    return 0;
}

測試數(shù)據(jù)：

thisismytext[thisismytext-1
thisismytext-1thisismytext