(1:14) いつの間にか、出張（見学）に行く前日だ。
明日の仕事が終わってから出発して、東京で一泊して、明日一日見学して帰ってくることになる。
考えてみると、スーツを着ないといけないだろうか。
面倒だなぁ。
明日は原付で出退勤してから着替えて東京に行くことにするか。
雨が降るかもしれないけど…。
そういえば、この前ちょっと触れた「いつものやり方」について。
文字列などについて、トライを作るほどじゃないけど、トライのノードについて何かをしたいということがよくある。
例えば、文字列のセットの中で、その最長接頭辞になるものを知りたいとか。
"A", "AA", "AAB", "ABA", "AC", "ACB", "ACC" という文字列セットがあるとき、"ACC" の最長接頭辞は "AC" だ、みたいなの。
こういうとき、ぼくはだいたいこの文字列セットをソートして、前の文字列との「違い」の場所を調べて、それによって最長接頭辞を求めるというやり方をよくする。
この例でいうと、文字列のセットをソートすると次のようになる。
A
AA
AAB
AC
ACB
ACC
最初は空文字列から始めるとする。
そして、長さ0に対する最長接頭辞として空文字列を記録する。
"A" の時点では、前の文字列（空文字列）との「違い」の位置は0。
最長接頭辞は、長さ0に対するものなので空文字列になる。
そして、"A" の長さである1に対して"A"を最長接頭辞として登録する。
"AA"の時点では、前の文字列（"A"）との「違い」の位置は1。
1に対応する文字列 "A" が最長接頭辞。
"AA"の長さである2に対して"AA"を記録。
"AAB"の時点では、「違い」は2。
"AA"が最長接頭辞。
3に対して"AAB"を記録。
"ABA" では、「違い」は1。
"A"が最長接頭辞。
自身の長さは3なので、3に対して"ABA"を登録。
その途中の2に対する最長接頭辞は、1に対する"A"をコピー。
…こうして書くと面倒なようだけど、トライを書いたりするよりはずっと楽だ。
トライのライブラリを使うのと比べても、依存関係が減らせていい。
しかし、このアルゴリズムの名前を実は知らない。
自分以外で使っている人も見たことがない。
まあ、トライを作るのをさぼれるというだけだけど。
検索もしにくいので、情報があれば知りたいところ。
