【Python】最長共通部分文字列の問題の解法

問題

2 個の文字列が与えられたとき, 両方の文字列に含まれる文字列のうち最も長いも のを探し, その長さを答えるプログラムを作成せよ.
ここで, 文字列 s が文字列 t に含まれるとは, t の中に s が連続して現れることをい う. 空文字列, すなわち長さ 0 の文字列は, どんな文字列にも含まれる. 例えば, 文字 列 ABRACADABRA には次の文字列が含まれる: ABRA, RAC, D, ACADABRA, ABRACADABRA, 空文字列など. 一方, 文字列 ABRACADABRA には次の文字列は含まれない: ABRC, RAA, BA, K など.
JOI 2007/2008 本選 問題2

２つの文字列が与えられたときに、それらの最長共通部分文字列の長さを答える問題です。ここで部分文字列とは「元の文字列に含まれる連続した文字列」のことを指します。「連続した」という点がLCS問題とは異なる点に注意してください。

実装例１

s = input()
t = input()
n = len(s)
l, r = 0, 0
ans = 0
while l<n and r<n:
  if s[l:r+1] in t:
    ans = max(ans, r-l+1)
    r += 1
  else:
    l += 1
print(ans)

ある文字列がTの中に含まれているかどうかは、in を使うことで判定できます。これを利用し、S中のある区間がTに含まれているか判定し、含まれていれば ans を更新し区間を広げる、含まれていなければ区間を狭める or 次に区間へ、と繰り返すことで最長共通連続部分文字列を求めることができます。

実装例２

この問題はLCS問題と同じようにDP(動的計画法)を用いても解くことができます。

s = input()
t = input()

# 先頭に空文字を挿入
s = "#" + s
t = "#" + t

ans = 0

# dp[j]はj番目の文字を含む共通部分文字列の長さ
dp = [0] * len(t)
for i in range(1, len(s)):
  for j in reversed(range(len(t))):
    if s[i] == t[j]:
      dp[j] = dp[j-1] + 1
      ans = max(ans, dp[j])
    else:
      dp[j] = 0
print(ans)

ここでは一次元のdpを使い回しています。そのため j のループを逆からにしていることに注意してください。