15
11

More than 5 years have passed since last update.

アルゴリズム1000本ノック #2. Longest common substrings

Posted at

Problem

``````与えられた２つの文字列に対し, 共通で持つ部分文字列の最大長を求めよ.

``````

Solution

DP（ダイナミックプログラミング）の中では古典的な問題です。

２つの文字列を S1 と S2, それぞれの長さをM, Nとします.

これを一般化して, m[i][j] は S1[i] =S2[j] ならm[i-1][j-1]+1, そうでなければ0と値を求めていくことができます.

これがいわゆるボトムアップのダイナミックプログラミングです。

algorithms_dp_longest_common_substring.py
``````def LCS(s1, s2):
if not s1 or not s2:
return 0

len1, len2 = len(s1), len(s2)

# memorization
m = []
for i in range(len1):
m.append([0]*len2) #m[len1][len2]

lcs = 0

# set 1st index value
for i, ch in enumerate(s1):
if ch == s2[0]:
m[i][0] = 1
lcs = 1
for i, ch in enumerate(s2):
if ch == s1[0]:
m[0][i] = 1
lcs = 1

# m[i][j] stands for s1[i] and s2[j]
# is the m[i][j] th bit of a common substring
for i in range(1, len1):
for j in range(1, len2):
if s1[i] == s2[j]:
m[i][j] = m[i-1][j-1] + 1
lcs = max(m[i][j], lcs)
else:
m[i][j] = 0
return lcs
``````

この場合, 計算量と空間料は O(MN)となります.

Jave版のコードはこちら:

algorithms_dp_longest_common_substring.java
``````public class Solution
{
public static int LCS(String s1, String s2) {
int l1 = s1.length();
int l2 = s2.length();
if (l1 == 0 || l2 == 0) return 0; // no common strings

// memorization
int[][] m = new int[l1][l2];
int maxLen = 0;

// set 1st index value
for (int i = 0; i < l1; i++) {
if (s1.charAt(i) == s2.charAt(0)) {
m[i][0] = 1;
maxLen = 1;
} else m[i][0] = 0;
}
for (int i = 0; i < l2; i++) {
if (s2.charAt(i) == s1.charAt(0)) {
m[0][i] = 1;
maxLen = 1;
} else m[0][i] = 0;
}

// m[i][j] stands for s1.charAt(i) and s2.charAt(j)
// is the m[i][j] th bit of a common substring
for (int i = 1; i < l1; i++) {
for (int j = 1; j < l2; j++) {
if (s1.charAt(i) != s2.charAt(j)) m[i][j] = 0;
else {
m[i][j] = m[i-1][j-1] + 1;
maxLen = (m[i][j] > maxLen)? m[i][j] : maxLen;
}
}
}
return maxLen;
}
}
``````
15
11
0

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
15
11