問題タブ [lcs]

2 つの文字列の LCS(Longest Common Subsequence) を DP(Dynamic Programming) で見つけることができます。DP テーブルを追跡することで、LCS を取得できます。しかし、複数の LCS が存在する場合、それらすべてを取得するにはどうすればよいでしょうか?

例：

ここで、「ab」と「bc」は両方とも LCS です。

入力の未知の領域をどれだけ正確に再構築できるかを確認するために、ランダムな文字列間の最長共通部分列を計算するこのコードがあります。良い統計を取得するには、何度も繰り返す必要がありますが、現在の Python の実装は遅すぎます。pypyを使用しても、現在 1 回の実行に 21 秒かかります。理想的には 100 回実行したいと考えています。

私はそれをnumpyに変換しようとしましたが、実際にはもっと遅く実行されたので、うまくいかなかったに違いありません. このコードはどうにかして高速化できますか?

アップデート。以下のコメントに従って、と同じ長さのすべてのサブリストのlcses間に LCS を与える再帰を直接使用した方がよいでしょう。これを行うために、古典的な動的計画法 LCS アルゴリズムを何らかの方法で変更することは可能ですか?patterntext

LCS アルゴを使用して、C++ で独自の diff を実装しています。LCS アルゴ ペーパーを見て、SES (最短編集スクリプト) を見つけようとすると、行の変更が発生することがあります。次のグラフの例では、挿入と削除のみを示しています。したがって、グラフを逆方向にたどると、水平線が削除され、垂直線が挿入されます。「c」の変更ケースがある場合はどうなりますか? 水平線の後に垂直線が続くと想定しています。つまり、削除してから挿入すると、変更と見なされます。SES を直接作成している C++ のコードは見たことがありません。グラフを作成して反転させずにSESを作成する方法はわかりませんが、O(ND)またはより良い時間の複雑さを得ることができるより良い実装があるかもしれません。LCSを実装してグラフを作成し、それをトラバースできます。SESを作成するための正確なルールを事前に知りたいだけです。この場合、削除と挿入の2つの状態を維持する必要があるようです。行と見なされます変更しますか？変更点 3,4c4,6 を取得する次のファイルを参照してください (以下を参照)。誰かがこれを行っているサンプル コードを持っている場合、特に以下に示す現在の diff バイナリ形式での diff 出力の作成に関して、参照として役立ちます。ランタイムを最大化し、そのためにスペースを犠牲にしているため、このバージョンを使用していました。この場合、SES を作成するための正確な規則は、行の変更と見なされるために削除と挿入の 2 つの状態を維持する必要があるように思われますか? 変更点 3,4c4,6 を取得する次のファイルを参照してください (以下を参照)。誰かがこれを行っているサンプル コードを持っている場合、特に以下に示す現在の diff バイナリ形式での diff 出力の作成に関して、参照として役立ちます。ランタイムを最大化し、そのためにスペースを犠牲にしているため、このバージョンを使用していました。この場合、SES を作成するための正確な規則は、行の変更と見なされるために削除と挿入の 2 つの状態を維持する必要があるように思われますか? 変更点 3,4c4,6 を取得する次のファイルを参照してください (以下を参照)。誰かがこれを行っているサンプル コードを持っている場合、特に以下に示す現在の diff バイナリ形式での diff 出力の作成に関して、参照として役立ちます。ランタイムを最大化し、そのためにスペースを犠牲にしているため、このバージョンを使用していました。

グラフの SES 逆を示す例のグラフを含むドキュメントの 3 ページを参照してください。

http://www.xmailserver.org/diff2.pdf

Linuxで通常の差分を使用した変更差分の例

2 つの部分文字列の最長の共通部分文字列のすべての部分文字列を表示する方法 lcs の長さを計算する dp メソッドを知っていますが、lcs のすべての lcs コードを表示する方法

すべての lcs を見つける方法について、ネット上で適切な記事を見つけることができませんでした

文字列 1=abcabcaa 文字列 2=acbacba

すべての lcs

アババ アバカ abcba アカバ アカカ acbaa acbca

私は既に lcs を計算する dp メソッドを知っています。

これはウィキで見つけた

しかし、それを理解するのに苦労しています

私はこの ERLANG を初めて使用しますが、基本は知っています。これはスキームに似ていますが、より広いです。関数の作成方法は知っていますが、Longest Common Subsequence を取得する関数の作成に問題があります。

lcs(str1,str2)2 つの文字列を受け取り、整数を出力する関数です。

lcs(algorithm,logarithm)7作成できる最長の共通サブシーケンスはサイズが同じlgrithmであるため、出力7されます。

どんな答えでも大歓迎です。

一般的な LCS 問題とアルゴリズムを知っています。

こんな感じです：

しかし、ギャップ条件を追加するとどうなるでしょうか。

例えば：

視覚的表現:

これを解決するにはどうすればよいですか？

DP テーブルの作成方法を教えてください。