python - 2 つの文字列間で最適に一致する文字数を見つける (文字列の配置のようなものですが、いくつかの方法ではありません)

Question

私はPythonでこれをやろうとしています。私は2つのシーケンスを持っています:

seq1: 'ABCD E'

seq2: 'ARCB E'

seq1 と seq2 の両方の文字数を「カウント」したいとしますが、次の方法で、seq1 の A から seq2 の A に線を引き、同様に C--C と E--E を接続するとします。 connect B--B この接続線は C--C を結ぶ線と交差するので ... B---B または C--C のいずれかを数えたいのですが、線が交差しているので両方ではありません。 2 つの文字列間で作成できる接続。

これを行う方法はありますか？私がやろうとしていることには名前があると確信していますが、それがわからないため、可能な方法についてオンラインで検索することも難しくなります。

お手伝いありがとう。

Answer 1

最長の一般的なサブシーケンスの問題のように聞こえます。レーベンシュタイン距離の動的計画法アルゴリズムの簡略化されたバージョンがこれを解決します。

インターウェブ上には、LCS の Python 実装が多数あります。ウィキペディアが提供する疑似コードも、Python に変換するのは簡単です。