题目描述

你在输入文章的时候，键盘上的Home键和End键出了问题，会不定时的按下。你却不知道此问题，而是专心致志地打稿子，甚至显示器都没开。当你打开显示器之后，展现你面前的数一段悲剧文本。你的任务是在显示器打开前计算出这段悲剧的文本。给你一段按键的文本，其中’[‘表示Home键，’]‘表示End键，输入结束标志是文件结束符（EOF）。
输出一行，即这段悲剧文本。

输入包含多组数据，每组数据占一行，包含不超过100000个字母、下划线、字符”[“或者”]“。

输入

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

输出

BeijuThis_is_a__text  
Happy_Birthday_to_Tsinghua_University

原题（PDF）

在这里插入图片描述

算法分析

最简单的方法就是用数组去存储每次在首位输出的串和末尾的串，然后频繁的将尾部串strcat连接到首位串中，但是这样的算法会超时
因此我们这里采用链表。
在C语言的算法中用数组来模拟链表，而CPP中可以直接使用STL中的list容器加上list迭代器解决问题
这里着重讲一下C语言的算法，用next数组去存储当前字符的下一位下标比如，next[1]=2,就意味着指向下标为2的字符，我们需要将next[0]单独拿出来作为没有数据存储的“头节点”，因此串s要的有效范围为1～n，并且用cur变量来记录光标位置，用last来记录当前的尾部位置，光标始终在s[cur]的右边。

当s[i]==’[‘时，光标cur=0，光标到首部
当s[i]==’]‘时，光标cur=last，光标到末尾
当s[i]为字符时，根据光标的位置（模拟尾插法）next[i]=next[cur];next[cur]=i 然后让光标等于i，去处理下一个i，如果尾部和光标位置相同意味着最近的控制字符为’]’，则尾部也同样移向i的位置。

解题标程( C )

#include <stdio.h>
using namespace std;
#define maxl 100005
int main()
{
    char s[maxl];
    while(~scanf("%s",s+1))
    {
        int Next[maxl]={
    0};
        int cur=0,last=0;
        for (int i = 1; s[i]; ++i)
        {
            if(s[i]=='[')    cur=0;
            else if(s[i]==']')    cur=last; //last会停止在[的左边一个字符，让光标cur回到last来继续链接
            else
            {
                //链表插入操作（就类似于尾插法）
                Next[i]=Next[cur];  //（令i的后续等于cur的后续，i始终是大于cur的）（类似于p->next=l->next）
                Next[cur]=i;  //（令cur的后续等于i）（类似与l->next=p）
                //last的更新
                if(cur==last)    last=i;
                //cur的更新
                cur=i;
            }
        }
        for (int i = Next[0]; i != 0; i = Next[i])
            if (s[i]!='['&&s[i]!=']')
                printf("%c",s[i]);
        printf("\n");
    }
    return 0;
}

解题标程(CPP)

#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
using namespace std;
int main()
{
    char str[100005];
    list <char> s;
    while (scanf("%s",str)!=EOF)
    {
        list <char>::iterator it=s.begin();
        int n=strlen(str);
        for (int i=0;i<n;i++)
        {
            char ch=str[i];
            if (ch=='[') it=s.begin();
            else if(ch==']') it=s.end();
            else
            {
                it=s.insert(it,ch);
                it++;
            }
        }
        for (it=s.begin();it!=s.end();it++)
            printf("%c",*it);
        s.clear();
        printf("\n");
    }
    return 0;
}