BUPT OJ94. 最小距離クエリー

タイトルの説明
小文字aからzからなる文字列Sが与えられ、i番目の文字はS[i](下付き文字は0から)です.INSERT cではcが入力される文字です.文字列の末尾にこの文字を追加する必要があります.入力された文字は同じaからzの小文字であることを保証します.QUERY xではxは入力される整数の下付き文字です.この質問に対して、SとSで答える必要があります.[x]は等しく、xに最も近い距離である.入力は、xが現在の文字列で正当であることを保証します.例えばS=「abcaba」であり、INSERT aを操作するとSの末端にa文字が付加され、Sは「abcabaa」になる.次にQUERY 0を操作するのはS[0]=aのため、Sに現れる彼に最も近いaは下付き3の位置で、距離は3-0=3である.したがって3を出力すべきである.次に、QUERY 4 S[4]=bであれば、Sにおいて最も近いbが下付きで1に現れ、距離は4−1=3である.同様に3を出力しなければならない.初期文字列Sといくつかの操作が与えられ、QUERYごとに対応する距離を求める必要があります.
HINTは入力データが大きいため,C/C++ではscanfを用いてより速い読み込み速度を得ることを推奨する.アルゴリズムの複雑さにも注意してください.
入力フォーマット
入力された最初の行は正の整数T(T≦20)であり、テストデータのグループ数を表す.各入力データのセットの最初の行は、初期列Sである.2行目は正の整数m(1≦m≦100000)であり、合計動作の数を表す.次にm行、各行が1つの操作を表す.操作のフォーマットは上記の通りです.データは、いずれの場合もSの長さが100000を超えないことを保証する.
出力フォーマット
QUERY毎に求めた最小距離を出力する.Sの他の位置に同じ文字が存在しない場合は、-1を出力します.
入力サンプル

2
axb
3
INSERT a
QUERY 0
QUERY 1
explore
3
INSERT r
QUERY 7
QUERY 1

出力サンプル

3
-1
2
-1

長い間引きずっていたACコードは、普通のdp問題としてそんなに低いAC率を持つのも珍しい.状態遷移方程式:

dp[pre[temp]][1]=dp[i][0]=i-pre[temp];

それだけで

/*
USER_ID: test#birdstorm
PROBLEM: 94
SUBMISSION_TIME: 2014-03-27 22:20:04
*/
#include 
#include 
#define For(i,m,n) for(i=m;i1) dp[pre[temp]][1]=dp[i][0]=i-pre[temp];
            pre[temp]=i;
        }
        scanf("%d",&n);
        while(n--){
            scanf("%s",tmp);
            if(tmp[0]=='I'){
                scanf("%s",ch);
                temp=ch[0]-'a'; cnt[temp]++;
                if(cnt[temp]>1) dp[pre[temp]][1]=dp[i][0]=i-pre[temp];
                pre[temp]=i++;
            }
            else
            {
                scanf("%d",&x);
                temp=(MIN(dp[x][0],dp[x][1]));
                if(temp==INF) puts("-1");
                else printf("%d
",temp);
            }
        }
        For(j,0,i) dp[j][0]=dp[j][1]=INF;
    }
    return 0;
}