Longest Common Substring
2つの文字列 s1 と s2 が与えられます。部分文字列とは、文字列から取り出した、文字が途切れずに並んだ部分のことで、たとえば clockwork の ork が該当します。s1 と s2 に共通する最長の部分文字列を見つけ、その長さを返してください。両方の文字列に共通する文字がない場合、答えは 0 です。
関数
- s1string
- 最初の文字列
- s2string
- 2つ目の文字列
- 戻り値integer
- 両方の文字列に含まれる最長の文字ブロックの長さ
制約
1 ≤ s1.length ≤ 10001 ≤ s2.length ≤ 1000s1とs2は小文字の英字で構成されています。
例
- 入力
- s1 = "clockwork"s2 = "workshop"
- 出力
- 4
- 説明
workはclockworkを閉じてworkshopを開くため、長さ 4 の共通部分文字列であり、これより長いブロックは両方に現れません。
- 入力
- s1 = "hammer"s2 = "harmed"
- 出力
- 2
- 説明
haとmeはどちらの単語にも含まれていますが、3文字の連続した並びはありません。どちらの単語にも h、a、m、e がこの順番で含まれていますが、harmedでは a と m の間に r があります。
- 入力
- s1 = "fig"s2 = "plum"
- 出力
- 0
- 説明
- この2つの単語には共通する文字がないため、最長共通部分文字列は空で、その長さは0です。
発展問題
ローリングハッシュを使って、指定した長さ L の共通部分文字列が存在するかどうかをおよそ O(n + m) 時間で判定し、その後 L について二分探索できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべての開始位置のペアを比較すると、同じ作業を繰り返すことになります。
iとjから始まるブロックには、i+1とj+1から始まるブロックが含まれます。一方の答えをもう一方にも再利用してみましょう。位置の各ペアについて、より限定した質問をします。
s1[i]とs2[j]でちょうど終わる共通ブロックの長さはいくつでしょうか？2つの文字が異なる場合は0です。一致する場合は、その前にある2つの文字に対する答えに1を足したものです。空の接頭辞を表す行 0 と列 0 を 0 として、表
run[i][j]にそれらの長さを入力します。答えは表の最後のセルではなく、表の中で最も大きい値です。各セルが参照するのは左上の対角にあるセルだけなので、1 行を右から左へたどれば十分です。
解説
すべての開始位置の組み合わせから一致を伸ばすと、同じ文字を何度も読み直すことになります。代わりに、ブロックが終わる位置を見てみましょう。s1[i]とs2[j]で終わる共通ブロックは、両方の文字が異なる場合は空になり、同じ場合はそれぞれ2つ前の文字で終わるブロックより1文字長くなります。これらの長さを表にすれば、O(n × m)時間で答えが求まります。
すべての開始位置のペアから拡張する
正しいが、最大のテストでは終わらない
考え方
すべての共通部分文字列は、s1 のある位置 i と s2 のある位置 j から始まります。すべての組について、文字が一致している間は先へ進んでステップ数を数え、最大の数を答えとします。
繰り返しの多いテキストでは、先へ進む距離が長くなります。両方の文字列が a を1000個並べたものの場合、各組は短い方の接尾辞の末尾まで進みます。文字の比較回数は約3.3 × 10^8回です。(i, j) からの走査は、1文字後ろにずらした (i+1, j+1) からの走査全体を繰り返します。
アルゴリズム
best = 0を設定します。s1のすべてのiと、s2のすべてのjについて、k = 0を設定します。i+kとj+kの両方がそれぞれの文字列の範囲内にあり、s1[i+k] == s2[j+k]である間、kに1を加えます。- 最大の
kをbestに保持し、それを返します。
def longestCommonSubstring(s1, s2):
n, m = len(s1), len(s2)
best = 0
for i in range(n):
for j in range(m):
# Walk forward while the two strings agree
k = 0
while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
k += 1
if k > best:
best = k
return best各ペアで終わるブロックの長さの表
考え方
run[i][j]を、s1[i-1]とs2[j-1]でちょうど終わる最長共通部分文字列の長さとします。0行目と0列目には0を入れます。このような部分文字列には、両方の文字列の文字が含まれている必要があります。文字が異なる場合、該当する部分文字列は存在しないため、そのセルは0です。一致する場合、この部分文字列はこの文字のペアと、両方の文字列で1文字前に終わる部分文字列を合わせたものです。つまり、run[i-1][j-1] + 1です。共通部分文字列は必ずどこかで終わるため、答えは位置にかかわらず、セルの最大値です。
hammerとharmedの場合、h同士で1になり、a同士で2に伸び、その後rで部分文字列が途切れます。hammerの2つ目のmは、mとrが一致しなかった後にharmedのmと一致するため、長さ1から始まり、e同士で2になります。3に達するセルはありません。
セルごとに比較は1回です。テキストの内容にかかわらず、1000文字の文字列2つなら約100万回です。
アルゴリズム
runを、すべて0のn+1行m+1列で確保し、best = 0を設定します。iを1..nでループし、その内側でjを1..mでループして、s1[i-1]とs2[j-1]を比較します。- 一致した場合は、
run[i][j] = run[i-1][j-1] + 1を設定し、bestを更新します。 - 一致しない場合は、そのセルを0のままにします。
bestを返します。
def longestCommonSubstring(s1, s2):
n, m = len(s1), len(s2)
# run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
run = [[0] * (m + 1) for _ in range(n + 1)]
best = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i - 1] == s2[j - 1]:
run[i][j] = run[i - 1][j - 1] + 1
if run[i][j] > best:
best = run[i][j]
# a mismatch leaves run[i][j] at 0
return best1 行、右から左へ更新
考え方
各セルが読み取るのは、左上の斜め隣にあるセルだけです。そのため、jを右から左へ処理すれば、m+1個の数値を持つ1つの配列runで表を保持できます。run[j]に書き込むとき、スロットrun[j-1]には、まだs1の前の文字に対する値が保持されています。これが斜めのセルにあたります。
スロットには前の行の数値が残っているため、不一致の場合は明示的に0を書き込む必要があります。実行時間はO(n × m)のままで、メモリ使用量は約10^6個の数値から1001個に減ります。
アルゴリズム
m+1個のゼロからなる配列runを作成し、best = 0に設定します。s1の各文字chについて、jをmから 1 まで降順に確認します。ch == s2[j-1]の場合、run[j] = run[j-1] + 1に設定し、bestを更新します。- そうでない場合は、
run[j] = 0に設定します。 bestを返します。
def longestCommonSubstring(s1, s2):
m = len(s2)
# run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
run = [0] * (m + 1)
best = 0
for ch in s1:
# Right to left, so run[j-1] still holds the value from the previous letter of s1
for j in range(m, 0, -1):
if ch == s2[j - 1]:
run[j] = run[j - 1] + 1
if run[j] > best:
best = run[j]
else:
run[j] = 0
return best
落とし穴と境界ケース
- 最後のセルを返すこと。
run[n][m]は、最後の文字同士で終わるブロックだけを対象にします。abcとabdの場合は 0 ですが、abの場合は 2 になります。 - 一致しない場合に、大きい方の隣接値をコピーすること。それは最長共通部分列のルールであり、ブロックが文字を飛ばせるようになります。
hammerとharmedの場合、2 ではなく 4 が返されます。 - 1 行だけを左から右へ走査すること。対角の値は読み取る前に上書きされるため、
aとaaの場合に 2 が返されます。 - 1 行だけの場合にリセットを省略すること。
s1の前の文字から得た長さが残り、その後、存在しないブロックを伸ばしてしまいます。 - 範囲チェックをせずに総当たりの処理を行うこと。
zzzzとzzの場合、短い方の文字列の末尾を越えて読み取ります。
よくある質問3
最長共通部分文字列と最長共通部分列の違いは何ですか？
部分文字列は、途切れずに連続する文字の並びです。部分列は順序を保ちますが、間に文字が抜けていてもかまいません。hammer と harmed の最長共通部分文字列の長さは 2 で、最長共通部分列の長さは 4 です（hame）。表では、不一致があると部分文字列のセルは 0 にリセットされますが、部分列のセルには隣接する値のうち大きい方がコピーされます。
最長共通部分文字列の時間計算量はどれくらいですか？
動的計画法による解法は、O(n × m) の時間がかかり、1行で実装すればメモリ使用量は O(m) です。すべての開始位置のペアから拡張する方法は、最悪の場合 O(n × m × min(n, m)) です。接尾辞オートマトンを使えば、プログラムが大幅に長くなる代わりに、計算量はおよそ O(n + m) になります。
最長共通部分文字列そのものを返すにはどうすればよいですか？
あるセルがbestを上回るたびに、そのブロックが終わるs1内の位置iも記録します。最後に、その位置で終わるs1の部分文字列が、best文字分になります。厳密な大なり比較を使うことで、s1で最初に見つかった最長のブロックが保持されます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def longestCommonSubstring(s1, s2):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s1 = "clockwork" s2 = "workshop"
期待される出力
4