1

Hackerrankの String Function Calculation 問題を解決しようとしています。この問題では、入力として文字列が与えられ、入力文字列のすべての部分文字列の中で、次の関数の最大値を表す数値を出力するよう求められます。

f(s, t) = 部分文字列 's' が文字列 't' に現れる回数 * 部分文字列 's' の長さ

回答として以下を提出しました。

import Data.List

main :: IO()
main = do
    stringInput <- getLine
    print $ solution stringInput

solution :: String -> Int
solution input = maximum $ map sum $ map (map length) $ group $ sort $ substrings input

substrings :: String -> [String]
substrings s = tail . inits =<< tails s

アイデアは次のとおりでした。

  1. のすべての部分文字列を取得しますs。let s = "aaaaaa"; substrings s = ["a","aa","aaa","aaaa","aaaaa","aaaaaa","a","aa","aaa","aaaa","aaaaa","a","aa","aaa","aaaa","a","aa","aaa","a","aa","a"]

  2. 並べ替えます。["a","a","a","a","a","a","aa","aa","aa","aa","aa","aaa","aaa","aaa","aaa","aaaa" ,"aaaa","aaaa","aaaaa","aaaaa","aaaaaa"]

  3. グループ化します。[["a","a","a","a","a","a"],["aa","aa","aa","aa","aa"],["aaa","aaa","aaa","aaa"],["aaaa","aaaa","aaaa"],["aaaaa","aaaaa"],["aaaaaa"]]

  4. 各部分文字列の個々の長さを取得します。[[1,1,1,1,1,1],[2,2,2,2,2],[3,3,3,3],[4,4,4],[5,5],[6]]

  5. 結果のリストを合計します。[6,10,12,12,10,6].

  6. 最大値を取得します。12.

これは予備試験に合格します。ただし、送信すると、「ランタイムエラー」により、他のすべてのテストに失敗します。

テストケース番号 最初に失敗した 2 は、実行に 1.47 秒かかり、次の入力があります。

"aacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccb"

私が間違っていること、または何が起こっているのかを理解するのを手伝ってもらえますか?

4

2 に答える 2

1

これはうまくいきません。
このリストの中間製品はメモリに残り、これらの製品は大きいため、Sort は (メモリに関して) 非常にコストがかかります。記憶
違いです

より良いアプローチは、サフィックス配列を使用してから、 最長プレフィックス配列 (LCP) を 作成し、LCP 配列を 問題の残りの部分に使用することです。 O(n log2n)
Kasai's Algorithm in O(n)

計算LCP[i] and LCP[i+1] 等しい場合は、2 つの等しい部分文字列があることを意味します。このように進みます。

于 2015-12-25T20:13:50.303 に答える