最长公共子序列和最长公共子串

最长公共子序列（Longest Common Subsequence, LCS）和最长公共子串（Longest Common Substring）都是在字符串处理中常见的问题，二者的区别在于：

1. 最长公共子序列（LCS）：

   例如，字符串ABCBDAB和BDCABA的最长公共子序列是BCBA，长度为4。

• 子序列是指从原字符串中删除某些字符（可以不删除任何字符）而不改变字符顺序所得的序列。

• 两个字符串的最长公共子序列是指在这两个字符串中同时出现的、长度最长的子序列。

• LCS问题的特点是子序列中的字符不需要连续，但顺序必须保持一致。

2. 最长公共子串：

   例如，字符串ABCBDAB和BDCABA的最长公共子串是BD，长度为2。

• 子串是指从原字符串中截取的一个连续的部分。

• 两个字符串的最长公共子串是指在这两个字符串中同时出现的、长度最长的连续子串。

• 长度最长的公共子串要求子串中的字符必须是连续的。

总结来说，最长公共子序列允许不连续的字符，而最长公共子串要求字符必须是连续的。这导致了二者在实际问题中应用场景的不同。