こっぱみぢんこ

更に重ねて

ベランダから見た空の薄橙色が、浮世絵の空の色のようだった。東海道五十三次の日本橋だったか、あの空が確かこんな色だったような気がする。

+

またも最長重複文字列について。

結局、聖蹟桜ヶ丘の本屋で WEB+DB Press 総集編を買ってきたのだった。最長重複文字列の問題は、2012年2月の vol.67 に載っていた。もう1年以上前だったんだね。なんで店頭に残っていたんだろう。たぶん、店員がやる気が無いからだな。

さて、雑誌に載っていた回答だが、言われてみれば成る程と納得できるものだった。

与えられた文字列から接尾辞リストを作る。
ソートする。
隣り合う要素を組にする。
組となっている2つの文字列の共通部分の長さを求める。
共通部分が一番長い要素を取り出す。
共通部分のみを残す。

この方針で実装した Haskell の模範解答がこれ。


import Data.List

--最長重複文字列を計算する
maxDupStr :: [Char] -> [Char]
maxDupStr = extract . chooseMax . calcLen . makePair . sort . tails

--隣り合う要素を組にする
makePair :: [[Char]] -> [([Char], [Char])]
makePair xs = zip xs (tail xs)

--文字列の共通部分の長さを求める
calcLen :: [([Char], [Char])] -> [(Int, [Char])]
calcLen = map lenstr

lenstr :: ([Char],[Char]) -> (Int,[Char])
lenstr (xs,ys) = (comlen xs ys, xs)

comlen :: [Char] -> [Char] -> Int
comlen xs ys = length (takeWhile pairEq (zip xs ys))

pairEq :: (Char,Char) -> Bool
pairEq (x,y) = x == y

--共通部分が一番長い要素を取り出す
chooseMax :: [(Int,[Char])] -> (Int,[Char])
chooseMax = maximumBy compFst

compFst :: (Int,[Char]) -> (Int,[Char]) -> Ordering
compFst (n1,s1) (n2,s2) = compare n1 n2

--共通部分のみを残す
extract :: (Int, [Char]) -> [Char]
extract (i,xs) = take i xs

短い。リストを扱う便利な関数がある程度揃っているからってのもあるけど、それを割り引いても、俺の JavaScript 版と比べるとかなりコードが少ないよな。

いや、逆か。問題を、いかに既存のAPIが使えるように考えるか。こっちがポイントで、それが上手く出来ているからコードが短くできるのだな。

ああ、いや、これはまた逆なのか。関数型言語の威力が判り易い例をサンプルとして選んだのだろうから、この例題の関数型言語による回答がスッキリ奇麗なのは予定調和なんだよな。

ま、少なくともこの問題に対して、関数型言語の考え方が判り易いのは確かだよな。接尾辞リスト作って、ソートして、隣り合う要素から同じ部分を抜き出すってのは、入力と出力が奇麗に繋がってるし。

似たような方針で JavaScript でも作ってみた。


function search( s ) {
    return getLongest( getSameList( getTailList( s ) ) );
}
function getTailList( s ) {
    var list = [];
    for ( var i = 0; i < s.length; i++ ) {
        list.push( s.substring( i ) );
    }
    return list.sort();
}
function getSameList( list ) {
    var sameList = [];
    list.reduce( function ( i1, i2 ) {
        sameList.push( getSame( i1, i2 ) );
        return i2;
    } );
    return sameList;
}
function getSame( s1, s2 ) {
    for ( var i = 0; s1.charAt( i ) === s2.charAt( i ) && i < s1.length; i++ ) ;
    return s1.substring( 0, i );
}
function getLongest( list ) {
    return list.reduce( function ( i1, i2 ) {
        return i1.length >= i2.length ? i1 : i2;
    }, "" );
}

なんか、これまでとあまり代わり映えしないな。これが27行で、最初に作ったのが25行。むしろ長くなってるし。

最初の奴に比べてこっちが優れているのは、最長N回重複文字列への拡張が容易なこと。「隣り合う要素の同じ文字列で新しくリストを作る」という処理をN-1回繰り返して適用すればいいのだから。

ということで、上の奴を最長N回重複文字列取得用に変更。


function search( s, num ) {
    return getLongest( getSameList( getTailList( s ), num ) );
}
function getTailList( s ) {
    var list = [];
    for ( var i = 0; i < s.length; i++ ) {
        list.push( s.substring( i ) );
    }
    return list.sort();
}
function getSameList( list, num ) {
    if ( --num === 0 ) {
        return list;
    }
    var sameList = [];
    list.reduce( function ( i1, i2 ) {
        sameList.push( getSame( i1, i2 ) );
        return i2;
    } );
    return getSameList( sameList, num );
}
function getSame( s1, s2 ) {
    for ( var i = 0; s1.charAt( i ) === s2.charAt( i ) && i < s1.length; i++ ) ;
    return s1.substring( 0, i );
}
function getLongest( list ) {
    return list.reduce( function ( i1, i2 ) {
        return i1.length >= i2.length ? i1 : i2;
    }, "" );
}

前回の最長N回重複文字列版が38行だったのに対して、これは30行。およそ2割の減少ってのは、結構な改善だよな。って、改善の根本が人のアイデアってのが駄目な感じだけど。前回、接尾辞リストを作るところまではいってたのだから、もうちょっと考えりゃ良かったな。

ところで、勝手に「末尾文字列」と名付けてリストを作っていたのだが、これにはちゃんと「接尾辞リスト」って名前がついてたんだね。

2013 06 15

更に重ねて

+