LRJ入门经典（基础篇）——4.悲剧文本

4.悲剧文本

问题描述：
你有一个破损的键盘。键盘上所有的键都可以正常工作，但有时候Home键或者End键会自动按下。你并不知道键盘存在这一问题，而是专心打稿子，甚至连显示器都没打开。当你打开显示器后，展现在你面前的是一段悲剧文本。你的任务是在打开显示器之前计算出这段悲剧文本。
输入包含多组数据。每组数据占一行，包含不超过100000个字母、下划线、字符“【”或者“】”。其中字符“【”表示Home键，“】”表示End键。输入结束标志为文件结束符（EOF）。输入文件不超过5MB。对于每组数据，输出一行，即屏幕上的悲剧文本。

样例输入：

This_is_a_[Beiju]_text

样例输出：

BeijuThis_is_a_text
分析：
如果使用数组来存储该输入文本，当遇到''["(home)键时继续输入文本会产生大量的位移操作，浪费大量的时间这里我们可以采用链表。这个问题中我采用的是静态链表。解题思路：想象在编辑文档时候的情形，用一个链表表示输入的字符，有一个可任意移动的光标，可以在光标的位置插入字符，我们在程序中要存储光标的位置，最后一个字符的位置。

#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;
}

测试数据：

thisismytext[thisismytext-1
thisismytext-1thisismytext