[UVA]UVA – 11988 Broken Keyboard (a.k.a. Beiju Text) – 破损的键盘(又名:悲剧文本)

题目地址:

https://cn.vjudge.net/problem/UVA-11988

题目描述:

(爱词霸翻译)

Background
背景

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).
你带着一个破碎的键盘输入的长文本。这是不是太严重了。用键盘的唯一问题是,有时“Home”键或“End”键会自动按下。

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.
你没有意识到这个问题,因为你专注于文本,甚至没有打开监视器!你打完后,你可以看到屏幕上的文本(如果你打开显示器)。
在中国,我们可以叫它悲剧。你的任务是找到悲剧的文字。

The 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).
有几个测试用例。每个测试用例都是一行,包含至少一个和至多100000个字母、下划线和两个特殊字符 ‘[’ 和 ‘]’。 ‘[’意味着“Home”键在内部被按下,‘]’ 意味着内部的“End”键被按下。输入由文件结尾(EOF)终止。

The 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


我的分析

虽然知道本题要使用链表,可是我只想用传统的链表(定义链表结构体,在结构体中存放一个指向下一个元素的指针,然后操作)去做。这样的结果就是摸不清OJ的脾气。uDebug上的用例有时能过有时不能过。看来结构体也只能和一些容器合并使用,作为数据的存储类型还是可以的。

我想过要用STL里面的list去做,可是这个list并不能直接找到链表中某元素的位置,只能读取begin和end。

所以还是老老实实的用刘汝佳的办法,他的办法确实最简单。通过一个next的整形数组为每一个字符指定其下一个字符的位置,就等于我之前所定义的next指针。然后令我比较惊讶的是,由于字符串首部的s[0]为空,而next[0]又初始化为0,则在next数组的填充过程中,0一直都是最后一个元素对应的next数组的值。因为它会不停地往后传递。所以最后输出时,是通过i等于0作为结束条件的。

最后,由于我将fgets改成scanf之后,忘记补结束条件EOF,导致超时好几次。

代码

先上刘汝佳的代码。

再上我用struct怎么都过不了的代码。