例題6-4 UVA 11988 Broken Keyboard(a.k.a.Beiju Text)破損したキーボード

1018 ワード

興味深いテーマです
「HOMEに変換」をendキーに変換して最後に出力すればいいです.
例題にはチェーンテーブルを用いて,この問題のチェーンテーブルを簡単に記録した.
チェーン時計はいろいろありますが、自分は構造体のチェーン時計に限られていることもわかりました!
カーソル位置をcurで記録し、lastは最後の文字を表し、next配列で各文字が次の文字に接続されているかを記録します.
最後にnext配列のシーケンス番号を出力すればいい!
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100000 + 10;
char s[maxn];
int cur,last,next[maxn];
int main()
{
    while(scanf("%s",s+1) == 1){
        int len = strlen(s+1);
        cur = last = next[0] = 0;
        for (int i = 1; i <= len; ++i){
            char ch = s[i];
            if (ch == '[')cur = 0;
            else if (ch == ']')cur = last;
            else{
                next[i] = next[cur];
                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("
"); } return 0; }