Pythonで指定された2つの文字列の一般的な特殊な部分文字列のサイズを見つけるプログラム

2つの文字列s1とs2があるとします。 s1とs2の両方の特別なサブストリングである最長のストリングs3のサイズを見つける必要があります。

yから0個以上の文字を削除してxを生成できる場合、文字列xは別の文字列yの特別な部分文字列であると言えます。

したがって、入力がs1='パイナップル's2='people'の場合、特別な部分文字列はサイズ5の' peple'であるため、出力は5になります。

これを解決するには、次の手順に従います-

• prev：=新しい辞書。キーが存在しない場合は0を返します
• 範囲0からs1-1のサイズのiの場合、do
  • cur：=新しい辞書。キーが存在しない場合は0を返します
  • 範囲0からs2-1のサイズのjの場合、do
    • cur [j]：=prev [j-1] + 1（s1[i]がs2[j]と同じ場合）それ以外の場合はcur[j-1]とprev[j]の最大値
  • prev：=cur
• return prev [size of s2 -1]

例

理解を深めるために、次の実装を見てみましょう-

from collections import defaultdict
def solve(s1, s2):
   prev = defaultdict(int)
   for i in range(len(s1)):
      cur = defaultdict(int)
      for j in range(len(s2)):
         cur[j] = prev[j - 1] + 1 if s1[i] == s2[j] else max(cur[j - 1], prev[j])
      prev = cur
   return prev[len(s2)-1]

s1 = 'pineapple'
s2 = 'people'
print(solve(s1, s2))

入力

'pineapple', 'people'

出力

5