問題タブ [lcs]

同じ長さの 2 つの文字列があります。そして、Y と Z が空でない XYZ と XZY として表現できるかどうかを確認する必要があります。

私の解決策は、両方の文字列の同じ最初の文字を「食べ」、残りの最長共通部分文字列を見つけることです。次に、最初の文字列の残りと 2 番目の文字列の残り (LCS なし) が等しいかどうかを確認します。問題は、このための O(N) メモリ複雑性アルゴリズムについて聞いたことですが、私が見つけたのは O(MN) だけです。私は記憶力が限られているので、それは私にとって重要です。

2 番目の解決策は、"(.*)(.+)(.+)\1\3\2" 正規表現を使用することですが、これは非常に貧弱な解決策です。

他のアイデアはありますか？

LCS テーブルを描画しようとしています。そして、コードのこの部分は、fill_the_table()関数の内側の while ループの最初の繰り返しの後に停止します。コードの何が問題なのかわかりません。ちなみに、私はC++の初心者です...

1. int** tableとを からにint** p渡した方法で渡すことはできますか?table()fill_the_table()
2. vector<string>ファイル自体を読み取る代わりに使用することを提案する人がいますが、どちらが望ましいですか?

それらがどのように機能するかに関して、私は低レベルの作業について疑問に思っていました:

1. マージの競合を引き起こすのは何ですか?
2. コンテキストは、パッチを適用するためにツールでも使用されますか?
3. 実際にはソース コードの動作を変更しない変更にどのように対処するのでしょうか? たとえば、関数定義の場所を交換します。

安全性に関しては、正直なところ、巨大な Linux カーネル リポジトリが安全性の証です。ただ、以下の点が気になります。

1. ユーザーが知っておくべきツールに関する警告/制限はありますか?
2. アルゴリズムが間違った結果を生成しないことが証明されていますか?
3. そうでない場合、少なくとも経験的にエラーがないことを証明する統合テストを提案する実装​​/論文はありますか? これらの論文BrianKorverとJamesCplienの内容のようなもの。
4. 繰り返しますが、前の点に関しては Linux リポジトリで十分ですが、もっと一般的なものについて疑問に思っていました。ソース コードは、変更されても (特に実装されているアルゴリズムと構文の制限により) あまり変更されませんが、安全性を一般的なテキスト ファイルに一般化できますか?

編集

わかりました、質問があいまいで、回答が詳細に対応していないため、編集しています。

Git/差分/パッチの詳細

Git がデフォルトで使用しているように見える統合 diff 形式は、基本的に 3 つのものを出力します: 変更、変更を取り巻くコンテキスト、およびコンテキストに関連する行番号です。これらのそれぞれが同時に変更されている場合とされていない場合があるため、Git は基本的に 8 つの可能性のあるケースに対処する必要があります。

たとえば、コンテキストの前に行が追加または削除された場合、行番号は異なります。ただし、コンテキストと変更が同じままである場合、diff はコンテキスト自体を使用してテキストを整列させ、パッチを適用できます (これが実際に発生するかどうかはわかりません)。さて、他のケースではどうなるでしょうか？Git が変更を自動的に適用することを決定する方法と、エラーを発行してユーザーに競合を解決させることを決定する時期の詳細を知りたいです。

信頼性

Git にはコミットの完全な履歴があり、履歴をトラバースできるため、Git は完全に信頼できると確信しています。私が望むのは、学術研究へのいくつかの指針と、これに関する参考文献が存在する場合です。

この主題に少し関連していますが、Git/diff はファイルを一般的なテキスト ファイルとして扱い、行で動作することを知っています。さらに、diff で採用されている LCS アルゴリズムは、変更の数を最小限に抑えようとするパッチを生成します。

そこで、私も知りたいことがいくつかあります。

1. 他の文字列メトリック アルゴリズムの代わりに LCS が使用されるのはなぜですか?
2. LCS が使用されている場合、基礎となる言語の文法的側面を考慮したメトリックの修正版を使用しないのはなぜですか?
3. 文法的な側面を考慮したそのような測定基準が使用される場合、それらは利益をもたらすでしょうか? この場合の利点は、たとえば、よりクリーンな「責任ログ」など、何でもかまいません。

繰り返しになりますが、これらは巨大なトピックになる可能性があり、学術論文は大歓迎です。

問題は、任意の配列の LIS (最長増加部分列) を見つけることです。元。[] = {10,9,7,8,9}; 長さ=3; {7,8,9}

したがって、nlognで行う1つの方法は

1. 配列をソートする
2. 2 つの LCS を取り、結果として LIS が得られます。

今、私はそれを行う方法を理解しました。しかし、それが正しいことをどのように証明するのでしょうか。ここで MI を適用する方法は?

秋学期は動的計画法理論を勉強しましたが、ブラッシュアップしてさらに勉強を続けようと思っています。私は現在、この TopCoder 記事で述べられているように、LCS 問題への単純なアプローチを試みています:動的プログラミング

アルゴリズムは次のとおりです。

たとえば、文字列「ABCDE」と「DACACBE」の場合、最も長い共通サブシーケンスは「ACE」です。

ただし、正しい「ACE」ではなく、有効な部分文字列「ABE」を出力します。実装の順序の何が問題になっていますか?

O(2^n)Longest Common Subsequence アルゴリズムの再帰関数の複雑さがわかりません。

通常、この表記法はアルゴリズムの基本操作 (この場合は比較) の数と関連付けることができますが、今回は意味がありません。

たとえば、同じ長さの 2 つの文字列があるとし5ます。最悪の場合、再帰関数は251比較を計算します。そして2^5、その値にさえ近くありません。

この関数のアルゴリズムの複雑さを説明できる人はいますか?

2 つの文字列が共有する共通のパターンを識別する (簡単な) 可能性はありますか? 私が言いたいことを明確にするための小さな例を次に示します。

文字列を含む 2 つの変数があります。どちらも同じパターン (「ABC」) といくつかの「ノイズ」を含んでいます。

一般的なパターンがわからないので、両方の文字列に「ABC」が含まれていることを R に確認させたいとします。これどうやってするの？

*編集

最初の例は少し単純すぎたかもしれません。これが私の実際のデータの例です。

どちらの文字列にも、関数で識別したい「DUISBURG」が含まれています。

*編集

コメントに投稿されたリンクで提案された解決策を採用しました。しかし、私はまだ欲しいものを正確に持っていません。

関数が 2 つのベクトルの最長の共通サブシーケンスを探している場合、なぜ の後で停止しないの"D" "U" "I" "S" "B" "U" "R" "G"ですか? .