Yukicoder No.69 文字を自由に並び替え

solution

高級言語で書くなら、ソートして一致するか見ればよい。$O(N \log N)$。 そうでなければ、rolling hashのように多項式を使ったhash関数$H(x) = \sum f(x_i)$を用いて比較する。加算に$O(a)$で乗算を$O(b)$と仮定すると$O(N(a + b)^{\mathrm{deg}(f)})$。

implementation

提出: https://yukicoder.me/submissions/202298

整形前

#!/usr/bin/env bfi
>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> O
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> N
>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> S
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> E
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> Y
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> V
[ +[-<+] ]
#
+[->,+]
<-[+[-<]>[>]<-]
<[-<]
<[>>[>]+[>]<[-<]<-]

#
>>[>]>[>]<
[
    >+++>+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]
    >[<<[<]<[<]<+>>[>]>[>]>-]
    <<[-]
    <
]
#
<[
    >+++>+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]
    >[<<[<]<->>[>]>-]
    <<[-]
    <
]
<[<]<[.<]
daaaaaaaaa
bbbbbbbbba