Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで3つ以上の文字列から最長の共通部分文字列を見つける方法は？

最長共通部分文字列アルゴリズムの一般的な動的計画法の実装は、O（nm）時間で実行されます。以下は、最も長い一般的な部分文字列アルゴリズムの実装です。

例 
def longest_common_substring(s1, s2):
   m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
   longest, x_longest = 0, 0
   for x in xrange(1, 1 + len(s1)):
       for y in xrange(1, 1 + len(s2)):
           if s1[x - 1] == s2[y - 1]:
               m[x][y] = m[x - 1][y - 1] + 1
               if m[x][y] > longest:
                   longest = m[x][y]
                   x_longest = x
           else:
               m[x][y] = 0
   return s1[x_longest - longest: x_longest]
print(longest_common_substring('wellbeing', 'welcome'))
出力 
wel
これがその仕組みです

  • 最初に、counter array（m）all0を初期化しました。

  • 1行目から、文字列s1の最初の文字を文字列s2のすべての文字と比較します。

  • s2の文字をトラバースしているときに、s1の文字と一致する場合は、カウンターをインクリメントします。対角線上1つ下の位置にあるm[i][j]が保存されます。

最後に、ループで計算したインデックスを使用して、最長のサブ文字列を返します。


  1. 2つの文字列から珍しい単語を見つけるPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 − 2つの文字列が与えられているので、与えられた文字列から珍しい単語を取得する必要があります。 次に、以下の実装のソリューションを見てみましょう- 例 # uncommon words def find(A, B):    # count    count = {}    # insert in A    for word in A.split():       count[word] = coun

  2. 2つのソートされた配列から最も近いペアを見つけるためのPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 − 2つの配列が与えられたので、2つのソートされた配列から最も近いペアを見つける必要があります 次に、以下の実装のソリューションを見てみましょう- 例 # sys module import sys # pair def print_(ar1, ar2, m, n, x):    # difference    diff=sys.maxsize    # index    l = 0    r = n-1 &