こっぱみぢんこ

重ね重ね

先日の最長重複文字列について正解を確認しようと本屋に行ったのだが、目当ての本が見当たらなかった。売れてしまったのか、場所を移されたのか。無いと思うとよけいに答えが気になるな。他の本屋を当ってみるか。過去分の全てがPDF化された総集編を売ってたはずだから、そっちを買ってくるかな。

せっかくなので、先日の問題を拡張してみよう。

最長N回重複文字列を探すプログラムを作れ。ここでNは2以上の任意の整数とする。例えば

Ask not what your country can do for you, but what you can do for your country.

であれば、最長3回重複文字列は「 you」となる。最長4回重複文字列も同じ。

オリジナルが2回限定なのを、3回以上繰り返し現れる文字列の最も長いものとか、4回以上とか、要は数が指定できるようにしようということ。

先日のは、

ある位置から後ろの文字列を取り出す。
その先頭と同じ文字を後ろに向かって探す。
有れば、先頭、その位置、それぞれから後ろに続く文字が同じだけ取り出す。

というのを先頭から繰り返し、そのそれぞれで取り出されたものの家で最も長いものを答えとしていた。

これ、重複が2限定だからスッキリ書けるんだよな。 N回となると、上の手順の2番目を「先頭と同じ文字が後ろにN-1回存在すること」と拡張し、このそれぞれで続く文字を調べなければならない。それだけでも面倒そうなのに、同じ文字はN回以上有る可能性もあって、先日の拡張ではきっと破綻してしまう。

ということで、別の方法を考える。

考えた。

結果、浮かんできたのはこんな方法。

問題の文字列から、先頭から末尾まで、2文字目から末尾まで、3文字目から末尾まで… と部分文字列を取り出す。頭を取り除いた末尾までの部分文字列なので、ここではこれらを末尾文字列と呼ぶことにしよう。この操作で、問題の文字列の文字数と同じだけの末尾文字列ができることになる。
末尾文字列を先頭の文字が同じものに仕分けする。
仕分けした結果、指定のNよりもメンバーが少ないグループは切り捨てる。これらはN回重複文字列にはなり得ないからね。
残ったグループのそれぞれで2文字目が同じものに仕分けする。
仕分けした結果、指定のNよりもメンバーが少ないグループは切り捨てる。
各グループで、下のグループが無くなるまで、N文字目でのグルーピングと切り捨ての繰り返し。
全滅する直前に残っていたグループのメンバーに先頭から共通する文字列を取り出す。これらがN回重複文字列。
N回重複文字列の最も長いものをとりだす。これが求める最長N回重複文字列。

要は仕分けと切り捨ての繰り返し。繰り返しと言うよりは、結果への再適用と言った方が適切か。ま、何れにしても、同じ処理を繰り返し適用するという形にできれば、プログラムはもう7割ぐらい出来た感じなんだよな。

で、この方法を実装した結果。


function search( s, num ) {
    return subSearch( toTailList( s ), "", num );
}
function subSearch( list, head, num ) {
    var answer = "";
    var hash = lowCut( toTailHash( list, head.length ), num );
    for ( var c in hash ) {
        answer = getLonger( answer, subSearch( hash[ c ], head + c, num ) );
    }
    return answer ? answer : head;
}
function toTailList( s ) {
    var list = [];
    for ( var i = 0; i < s.length; i++ ) {
        list.push( s.slice( i ) );
    }
    return list;
}
function toTailHash( list, pos ) {
    var hash = {};
    list.forEach( function ( s ) {
        var c = s.charAt( pos );
        ( hash[ c ] = hash[ c ] || [] ).push( s );
    } );
    return hash;
}
function lowCut( hash, num ) {
    var remain = {};
    for ( var c in hash ) {
        if ( hash[ c ].length >= num ) {
            remain[ c ] = hash[ c ];
        }
    }
    return remain;
}
function getLonger( s1, s2 ) {
    return s1.length >= s2.length ? s1 : s2;
}

だいたい手順で書いた通りだが、ちょっと違うのがN回重複文字列から最長N回重複文字列を決めるところ。 N回重複文字列全体を最後に比較して最長を決めるような書き方をしているが、実際はグループ内でN回重複文字列が決まる毎に、それまでの最長と比較して短いのを捨てている。

以下、各関数の処理概要。

search( s, num ): 文字列 s から、最長 num 回重複文字列を取り出す。
subSearch( list, head, num ): 処理の中核。末尾文字列の配列 list に対して仕分けと切り捨てを繰り返し、最長 num 回重複文字列を取り出す。
toTailList( s ): 文字列 s から末尾文字列の配列を作る。
toTailHash( list, pos ): 末尾文字列の配列 list を、pos 文字目の文字で仕分けする。具体的には、pos 文字目の文字を key、この位置の文字が同じ末尾文字列の配列を value とする連想配列を作る。
lowCut( hash, num ): 仕分け結果の連想配列から value である配列の要素数が num より少ないものを削除する。
getLonger( s1, s2 ): 文字列 s1 と s2 で長い方を返す。

概要としてさらっと書いたけど、subSearch はちょっと複雑なので補足。

末尾文字列の配列 list は、その要素が全て文字列 head から始まっていて、要素数は num 個以上。この次の文字でまた仕分けと切り捨てをするために、subSearch を再帰的に実行する。

head の後ろにに仕分けする文字を付けて渡すのは、仕分けの文字位置と、そこまでに同じであると確定している文字列とを、再帰の先で知るため。

切り捨てた結果が何も残らなくなったら、それはつまり head までは num 回重複してたけどその先が無かったということ。なので、このグループの結果として head を返す。

それぞれのグループが結果を返す毎に、それまでの最長と比べて長い方を新しい最長とする。最終的に残ったのが、最長 num 回重複文字列となる。

んー… やっぱり言葉で色々書くよりもコードを見た方が早いような気がするな。

エラーチェックとか何もしていないけど、num は2以上 s の文字数以下でなければ意味が無い。いや、これこそ言葉じゃなくコードで、つまりはエラー処理で示すべきことか。けどまあ、最長N回重複文字列を取得するのに、わざわざ1回を指定する奴はいないよな。うん、いない。するな。

2013 06 10

重ね重ね