UVa 11988 (数组模拟链表) Broken Keyboard (a.k.a. Beiju Text)
题意：
模拟一个文本编辑器，可以输入字母数字下划线，如果遇到'['则认为是Home键，如果是']'则认作End键。
问最终屏幕上显示的结果是什么字符串。
分析：
如果在数组用大量的移动字符必然很耗时。所以next数组表示显示屏中s[i]右边的字符编号，变量cur模拟光标，即当前光标位于s[cur]的右边。
变量last记录显示屏最后一个字符的下标。
我理解的连接的情况应该是这样子的：
1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 5 const int maxn = 100000 + 10; 6 int last, cur, next[maxn]; 7 char s[maxn]; 8 9 int main(void) 10 { 11 #ifdef LOCAL 12 freopen("11988in.txt", "r", stdin); 13 #endif 14 15 while(scanf("%s", s + 1) == 1) 16 { 17 int n = strlen(s + 1); 18 last = cur = 0; 19 next[0] = 0; 20 21 for(int i = 1; i <= n; ++i) 22 { 23 char ch = s[i]; 24 if(s[i] == '[') cur = 0; 25 else if(s[i] == ']') cur = last; 26 else 27 { 28 next[i] = next[cur]; 29 next[cur] = i; 30 if(cur == last) last = i; //更新最后一个字符编号 31 cur = i; //移动光标 32 } 33 } 34 35 for(int i = next[0]; i != 0; i = next[i]) 36 printf("%c", s[i]); 37 puts(""); 38 } 39 40 return 0; 41 }