2

KMPアルゴリズムの失敗テーブルを実装しました。

kmp s = b
    where a = listArray (0,length s-1) s
          b = 0:list 0 (tail s)
          list _ [] = [] 
          list n (x:xs) 
            | x==a!n    = (n+1):list (n+1) xs
            | n > 0     = list (b!!(n-1)) (x:xs)
            | otherwise = 0:list 0 xs

bはリストでb!!(n-1)、最後の行は遅いので、スピードを上げて次のようにしました。

kmp s = b
    where a = listArray (0,length s-1) s
          t = listArray (0,length s-1) b
          b = 0:list 0 (tail s)
          list _ [] = [] 
          list n (x:xs) 
            | x==a!n    = (n+1):list (n+1) xs
            | n > 0     = list (t!(n-1)) (x:xs)
            | otherwise = 0:list 0 xs

唯一の違いは、から生成b!!された配列であるt!と宣言することです。tb

同じ入力に対して、元のコードは正しい出力を持ちますが、新しいコードは単にを出力します<<loop>>。

どうすればこの問題を解決できますか？

4

2 に答える 2

3

あなたの問題は、リストがその構造（長さ）を決定するためbに配列を必要とすることです。tただし、配列tは存在する前にリストの長さが必要です。

listArray :: Ix i => (i,i) -> [e] -> Array i e
listArray (l,u) es = runST (ST $ \s1# ->
    case safeRangeSize (l,u)            of { n@(I# n#) ->
    case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
    let fillFromList i# xs s3# | i# ==# n# = s3#
                               | otherwise = case xs of
            []   -> s3#
            y:ys -> case writeArray# marr# i# y s3# of { s4# ->
                    fillFromList (i# +# 1#) ys s4# } in
    case fillFromList 0# es s2#         of { s3# ->
    done l u n marr# s3# }}})

ご覧のとおり、最初に適切なサイズの生の配列が割り当てられ、次にarrEleBottom（errorメッセージ未定義の配列要素を使用した呼び出し）で埋められ、次にリストがトラバースされ、リスト要素が配列（リスト要素）に書き込まれます。問題なく配列値を参照できます）。そして最後に、アレイがフリーズします。配列がフリーズされる前は、入力コードの外部から配列にアクセスすることはできません（基本的にはST s計算です）。

これを修正する最も簡単な方法は、ST sモナドで可変配列を使用するIMOです。

kmp s = elems b
  where
    l = length s - 1
    a = listArray (0, l) s
    b = runSTArray $ do
           t <- newArray_ (0,l)
           writeArray t 0 0
           let fill _ _ [] = return t
               fill i n (x:xs)
                 | x == a!n = do
                        writeArray t i (n+1)
                        fill (i+1) (n+1) xs
                 | n > 0    = do
                        k <- readArray t (n-1)
                        fill i k (x:xs)
                 | otherwise = do
                        writeArray t i 0
                        fill (i+1) 0 xs
           fill 1 0 (tail s)

コードの非常に直接的な（そして少し非効率的な）翻訳です。

于 2012-12-03T03:40:14.707 に答える
1

これはあなたの質問に直接答えるものではありませんが、STArrays.

アルゴリズムの命令型バージョンは、繰り返されるリストのインデックス付けや状態を使用せず、単に遅延配列構築を使用するバージョンに直接変換されます。

import Data.Array.IArray

kmp :: String -> Array Int Int
kmp s = b
  where
    a :: Array Int Char
    a = listArray (0,l-1) s
    b = listArray (1,l) (0:map (\q -> f (b!(q-1)) q) [2..l])
    f k q
      | k > 0 && (a ! k) /= (a ! (q-1)) =
        f (b ! k) q
      | a ! k == a ! (q-1) = k + 1
      | otherwise = k
    l = length s

ただし、私はこれをベンチマークしていません。

于 2012-12-03T06:49:09.753 に答える