最长连续公共子序列

注： 题目描述中提到的“如果有多个相同长度的子串符合要求，输出最后一个”，表述不够准确。此处应理解为在 s1 中靠后的那个子串。

解题思路

若两个字符串的最长连续公共子序列长度为n，删去其中的一些字符，我们总能得到长度为 n - k (k >= 0)的连续公共子序列。这体现出典型的二分性质，因此，我们使用二分法猜测公共子序列的长度。至于如何判断是否存在长度为m的子序列，可以将s2中所有长度为m的连续子序列加入哈希表中，并从后往前枚举s1的长度为m的连续子序列，判断其是否在哈希表中即可。因此判断子序列的时间复杂度为O(n^2)，加之二分法，总体时间复杂度为O(n^2 logn)，足以通过n <= 100的数据规模（其实n <= 100直接写个O(n^3)暴力也能过）。

解一（使用标准库哈希表）

#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>

bool check(const std::string& s1, const std::string& s2, int len, int& il1, int& ir1) {
    std::unordered_set<std::string> set;
    for (int i = 0; i + len <= s2.size(); i++) {
        set.insert(s2.substr(i, len));
    }
    for (int i = s1.size(); i - len >= 0; i--) {
        if (set.find(s1.substr(i - len, len)) != set.end()) {
            il1 = i - len;
            ir1 = i;
            return true;
        }
    }
    return false;...