学步园

The
simplest text editor "Open Word" allows to create and edit only one
word. The editor processes keys 'a' -- 'z', and also 'L' (to the left)
and 'R' (to the right). After starting his work the editor immediately
creates an empty word and sets its cursor to the left-most position.
When one of keys 'a' -- 'z' is pressed, the text editor inserts
corresponding symbol just after the cursor. After that a cursor moves
one position to the right in such a way that it is placed just after
new symbol. When key 'L' or 'R' is pressed, the cursor moves one
position to the left or to the right respectively. If the cursor can't
be moved because it is placed at the left-most or right-most position
the command is ignored. Developers of "Open Word" didn't think about
the effectiveness so the editor is working slowly if a lot of keys have
been pressed.

Your task is to write a program that can process a sequence of key pressings emulating this editor and output result string.

The input file contains one string which consists of symbols '
' -- '
', '
' and '
'. The string length is not less than 1 and doesn't exceed
.

Write a required string to the output file.

sample input

sample output

abLcd

acdb

sample input

sample output

icpLLLLLacmRRRRRRRRRRRRc

acmicpc

这个题目题意很简单，就是要写一个支持插入，左移光标，右移光标操作的文本编辑器，用双向链表就可以完美解决。但是我一开始用scanf("%s",str)将字符串都读入来再处理，就TLE on test54 后来改为读一个字符就处理一个字符，就AC了 ，966ms 汗一个-.-b

#include "iostream"<br /> #include "cstdio"<br /> #include "cstdlib"<br /> #include "cstring"<br /> using namespace std;<br /> typedef char elem_t ;<br /> typedef struct DLinkNode{<br /> elem_t data;<br /> DLinkNode* pre,*next;<br /> DLinkNode():data(0),pre(NULL),next(NULL){};<br /> void init(elem_t _data){<br /> data = _data;<br /> pre = next = NULL;<br /> }<br /> }DLinkNode;<br /> DLinkNode pool[1001010];;<br /> DLinkNode *pp;<br /> DLinkNode* getNode(){<br /> return pp++;<br /> }<br /> typedef struct DLink{<br /> DLinkNode* head,*tail;<br /> void init(){<br /> head = (DLinkNode*)malloc(sizeof(DLinkNode));<br /> tail = (DLinkNode*)malloc(sizeof(DLinkNode));<br /> head->pre = NULL;<br /> tail->next = NULL;<br /> head->next = tail;<br /> }<br /> void insert(DLinkNode* pos, DLinkNode* t){<br /> pos->next->pre = t;<br /> t->next = pos->next;<br /> t->pre = pos;<br /> pos->next = t;<br /> }<br /> }DLink;<br /> DLink* L;<br /> DLinkNode *cursor,*p;<br /> int main(){<br /> //printf("len = %d/n",strlen(str));<br /> pp = pool;<br /> L = (DLink*)malloc(sizeof(DLink));<br /> L->init();<br /> cursor = L->head;<br /> char ch;<br /> while(scanf("%c",&ch) != EOF){<br /> if(ch >= 'a' && ch <='z'){<br /> p = getNode();<br /> p->init(ch);<br /> L->insert(cursor,p);<br /> cursor = cursor->next;<br /> }else if(ch =='L' && cursor != L->head)<br /> cursor = cursor->pre;<br /> else if(ch == 'R' && cursor->next != L->tail)<br /> cursor = cursor->next;<br /> }<br /> for(p = L->head->next; p != L->tail; p = p->next)<br /> printf("%c",p->data);<br /> putchar('/n');<br /> return 0;<br /> }