LCS : longest common substring 即最長公共子串
LCS 問題就是求兩個字符串最長公共子串的問題洪唐。
解法就是用一個矩陣來記錄兩個字符串中所有位置的兩個字符之間的匹配情況涨冀，若是匹配則為1醉者，否則為0斟叼。然后求出對角線最長的1序列，其對應(yīng)的位置就是最長匹配子串的位置端逼。
但是在0和1的矩陣中找最長的1對角線序列又要花去一定的時間。通過改進(jìn)矩陣的生成方式和設(shè)置標(biāo)記變量洗贰，可以省去這部分時間。
當(dāng)字符匹配的時候陨倡，我們并不是簡單的給相應(yīng)元素賦上1敛滋，而是賦上其左上角元素的值加一。我們用兩個標(biāo)記變量來標(biāo)記矩陣中值最大的元素的位置兴革，在矩陣生成的過程中來判斷當(dāng)前生成的元素的值是不是最大的绎晃，據(jù)此來改變標(biāo)記變量的值，那么到矩陣完成的時候杂曲，最長匹配子串的位置和長度就已經(jīng)出來了庶艾。
算法的基本思想：
當(dāng)字符匹配的時候，不是簡單的給相應(yīng)元素賦上1擎勘，而是賦上其左上角元素的值加一咱揍。
我們用兩個標(biāo)記變量來標(biāo)記矩陣中值最大的元素的位置，在矩陣生成的過程中來判斷
當(dāng)前生成的元素的值是不是最大的棚饵，據(jù)此來改變標(biāo)記變量的值煤裙，那么到矩陣完成的時
候，最長匹配子串的位置和長度就已經(jīng)出來了蟹地。
C++ 實(shí)現(xiàn)
// std::format 為 C++20 特性
#include "stdc++.h"
using Table = std::vector<std::vector<int>>;
void print_table(const string& s1, const string& s2, const Table& t)
{
cout << " ";
std::for_each(s1.cbegin(), s1.cend(), [](char ch){cout << format("{:>3}", ch);});
cout << "\n";
for (size_t i = 0; i < s2.size(); i++) {
cout << format("{:>2}", s2[i]);
for (size_t j = 0; j < s1.size(); j++)
cout << format("{:>3}", t[i][j]);
cout << "\n";
}
}
string LCS(const string& s1, const string& s2)
{
size_t s1_len = s1.size(), s2_len = s2.size();
Table t(s2_len);
std::for_each(t.begin(), t.end(), [s1_len](auto& v){ v.resize(s1_len); });
size_t lcs_begin{}, lcs_end{}, lcs_len{};
for (size_t i = 0; i < s2_len; i++) {
for (size_t j =0; j < s1_len; j++) {
if (s1[j] == s2[i]) t[i][j] = (i == 0 or j == 0) ? 1 : t[i - 1][j - 1] + 1;
else t[i][j] = 0;
if (lcs_len < t[i][j]) { lcs_len = t[i][j]; lcs_end = j; }
}
}
print_table(s1, s2, t);
lcs_begin = lcs_end - lcs_len + 1;
return s1.substr(lcs_begin, lcs_len);
}
int main()
{
string s1{"hello,world,123"};
string s2{"HHHello,world,12345"};
string lcs = LCS(s1, s2);
cout << format("字符串: {} 和\n字符串: {} 的\n最長公共子串是：{}", s1, s2, lcs);
}
Python 實(shí)現(xiàn)：
# LCS : longest common substring 即最長公共子串
def print_table(s1, s2, t):
print("-"*20)
print(" ", end='')
for i in range(len(s1)):
print("{:>3}".format(s1[i]), end = '')
print("")
for i in range(len(s2)):
print("{:>2}".format(s2[i]), end = '')
for j in range(len(s1)):
print("{:>3}".format(t[i][j]), end = '')
print("")
def LCS(s1, s2):
print("尋找 {} 和 {} 的最大公共子串".format(s1, s2))
s1_len, s2_len = len(s1), len(s2)
t = [[0 for _ in range(s1_len)] for _ in range(s2_len)]
lcs_begin, lcs_end, lcs_len = 0, 0, 0
for i in range(s2_len):
for j in range(s1_len):
if s1[j] == s2[i]:
if i == 0 or j == 0: t[i][j] = 1
else: t[i][j] = t[i - 1][j - 1] + 1
else: t[i][j] = 0
if t[i][j] > lcs_len:
lcs_len = t[i][j]; lcs_end = j
print_table(s1, s2, t)
lcs_begin = lcs_end - lcs_len + 1
return s1[lcs_begin : lcs_end + 1]
if __name__ == '__main__':
strs = ["hello", "hell", "Hello", "llo", "hello, world"]
print("字符串列表：", strs)
lcs = strs[0]
for s in strs[1:]:
lcs = LCS(lcs, s)
print("字符串列表的最長公共子串是：{}".format(lcs))
