問題タブ [string-algorithm]

問題はここにあります: http://rosalind.info/problems/subs/

私が持っている質問は、以下に示す 2 つのソリューションのパフォーマンスに関係しています。

1.

2.

2 番目の解決策は、美しく機能的で短いものです。

最初のソリューションは少し大きいですが、それでも機能します。val を省略して、値を操作して短くすることもできましたが、それは私の目標ではありませんでした。

2番目の解決策を見た後、コードの長さのために私はかなりがっかりしました。scala ライブラリをチェックして、2 番目のソリューションが機能する理由を確認し、自分で再実装しました。両方のソリューションのパフォーマンスをチェックすることを考え、巨大な 3000 万の DNA ストランドを作成しました。

驚いた！

パフォーマンス：

最初の数字は DNA の長さで、次の 2 つの数字は 1 番目と 2 番目のソリューションの実行時間 (ms) を表します。

11,226,096 - 4921 - 14503

33,678,288 - 6448 - 35150

性能がこんなに違うのはなぜ？

scala ライブラリをチェックしてみましたが、この動作を説明するものは見つかりませんでした。

最初の解決策は多くのオブジェクトを作成するため、より多くのメモリを消費し、それを行うのに多くの時間がかかると思いましたが、何らかの理由ではるかに高速に動作するようです. 末尾の再帰ではないかと思いますし、zipWithIndex に時間がかかるとは思えません。イテレータは単なるイテレータですか?

ありがとう！

与えられたもの:
S、奇数個のn ビット文字列の集合
A、特定の n ビット文字列

A が S にあるかどうかを判断するアルゴリズムは、最悪の場合でも A の n ビットすべてを調べなければならないことを示してください。

もちろん、通常は文字列のすべての部分を調べてマッチングを行う必要があると予想されますが、 S のサイズが奇妙であることに特有の何かがあり、それが私を逃れています。

インタビューで弦について質問されました。問題には文字列s1= "ABCDBCCDABCD"が与えられます。そしてパターン「BC」。このパターンを他の文字列 ("UVW" または "U" または "uv") に置き換える必要があります。これは所定の位置に置く必要があります。

誰かがアルゴリズムと一緒にプログラムを提供してくれると助かります。

テキストの位置揃え (左右にフラッシュ) を実行する方法を実装しようとしています。各出力行の最大幅は M 文字です。単語の分割は許可されていません。

たとえば、次のウィキペディア ページの「両端揃え (左と右を揃える)」を参照してください: http://en.wikipedia.org/wiki/Justification_(typesetting)。

私は、最適な左寄せ、ぎざぎざの右寄せのための動的プログラミング ソリューションがあることを認識しています。つまり、余分なスペースのコストが最適になるように、行末に余分なスペースを均等に分配します (これは「ワード ラップ」とも呼ばれます)。 」の問題または「きれいに印刷する」問題)。ただし、全文正当化の問題に対する動的プログラミングまたは貪欲なアプローチに到達することはできません。

グーグルは、マルコフ連鎖プログラミングに基づくテキストの正当化に私を導きました: http://www.rose-hulman.edu/Users/faculty/young/OldFiles/CS-Classes/csse220/200820/web/Programs/Markov/justification.html。しかし、これは私には複雑に思えます。これが全文の正当化の問題に対する最良の (そして最も単純な) 解決策である場合、誰かが同じことを簡単な言葉で説明できれば素晴らしいことです。

予備的な注意: string_algo は問題なく動作しstd::wstring、string_algo のアルゴリズムが必要な場合は、最初に CString オブジェクトを std::wstring に変換できます (そして変換します)。ただし、CString オブジェクトをドロップできれば、非常に便利です。既存のコードとの統合がはるかに簡単になります。

私がしたいこと：

ここで提案されboost/range/mfc.hppているように、 Boost.Range を MFC に適合させるために追加で含めようとしました。(私はこのヘッダーをよく見ていませんが、CString に対しては何もせず、コレクション クラスに対してのみ行うようです。)

Visual Studio 2005 で 1.44.0 をブースト

テスト コードは次のようになります。

私が得るエラーは次のようになります：

入力文字列の可能な異なる巡回シフトの数を返す関数を作成する必要があります。

効率的な (時間の複雑さの点で) アルゴリズムを作成するには、どこから始めるべきかについてのヒントを教えてください。文字列の「前処理」から始めて、後でシフトをカウントするのに役立つデータ構造を作成する必要がありますか?

コードに問題が見つかりました。boost::algorithm::join を使用すると正常に動作しますが、boost::algorithm::join_if を使用すると bad_cast がスローされます。私のコードは以下の通りです：

私のプログラムの出力は次のとおりです。

テキストを操作するために boost::algorithm 関数を使用したことが あり、 predicateを使用したことはほとんどありませんでしたが、そのような問題は発生しませんでした。

const char* を std::string に置き換えようとさえしました:

しかし、問題はまだ同じです。

EDIT： C++ 11より古いC++でも機能するソリューションが欲しい

私は、さまざまなソースからコンパイルされた大都市のデータベースを持っています。都市名に基づいて重複を簡単に見つける方法を見つけようとしています。単純な答えは、レーベンシュタイン距離を使用することです。ただし、都市の問題は、多くの場合、その国で共通の接頭辞と接尾辞が付けられていることです。

例えば：

ブールビル対ボッシャービル

これらはほぼ確実に異なる都市です。ただし、どちらも "ville" で終わる (そしてどちらも "Bo" で始まる) ため、レーベンシュタイン距離はかなり小さくなります。

*文字の位置を考慮して、単語の途中の文字を単語の末尾の文字よりも高く重み付けすることで、接頭辞と接尾辞の影響を最小限に抑える文字列距離アルゴリズムを探しています。*

おそらく自分で何かを書くことはできますが、適切なアルゴリズムをまだ誰も公開していないとは信じがたいでしょう。