UVA11988 Broken Keyboard (a.k.a. Beiju Text)【数组模拟链表】

Output for the Sample Input

Happy_Birthday_to_Tsinghua_University

题目大意：你在输入文章的时候，键盘上的Home键和End键出了问题，会不定时的按下。

给你一段按键的文本，其中‘[‘表示Home键，‘]‘表示End键，输出这段悲剧的文本。

思路：使用链表来模拟，遇到Home键，就将后边的文本插入到这段文本的最前边，遇到

End键，就插入到这段文本的最后边。但是用链表会用到指针，过程比较繁琐。这里用一个

Next数组模拟指向，Next[i]表示当前显示屏中s[i]右边的字符下标。再用一个cur表示当前

光标的位置，last表示最后一个字符的记录位置，这样遇到End键，就能直接找到光标下一

个指向的字符位置了。

具体参考：算法竞赛入门经典（第二版）P143~144

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

char s[101000];
int Next[101000];

int main()
{
    int cur,last;//cur为光标位置，last为显示屏最后一个字符
    while(~scanf("%s",s+1))
    {
        memset(Next,0,sizeof(Next));
        int len = strlen(s+1);
        Next[0] = 0;
        cur = last = 0;
        for(int i = 1; i <= len; i++)
        {
            if(s[i] == '[')
                cur = 0;
            else if(s[i] == ']')
                cur = last;
            else
            {
                //模拟插入链表过程
                Next[i] = Next[cur];//第i个字符指向光标位置
                Next[cur] = i;//光标指向下一个字符
                if(cur == last)//只有光标在当前最后一个字符位置或是遇到]后才执行
                    last = i;
                cur = i;//移动光标
            }
        }
        for(int i = Next[0]; i != 0; i = Next[i])
            printf("%c",s[i]);
        printf("\n");
        memset(s,0,sizeof(s));
    }

    return 0;
}

UVA11988 Broken Keyboard (a.k.a. Beiju Text)【数组模拟链表】

原文：http://blog.csdn.net/lianai911/article/details/41831645