c++ - 如何查找所有以1开头和结尾的子串？

Question

给定一个由 0 和 1 组成的字符串，您必须找到该字符串中以 1 开头和结尾的所有子字符串。

例如，给定 0010110010，输出应该是六个字符串:

101
1011
1011001
11
11001
1001

显然有一个 O(N^2) 解决方案，但我正在寻找一个复杂度约为 O(N) 的解决方案。可能吗？

Answer 1

Obviously there is an O(N^2) solution, but I'm looking for a solution with complexity on the order of O(N). Is it possible?

令 k 为输入字符串中 1 的数量。那么就有O(k^2)这样的子串。枚举它们必须至少花费 O(k^2) 时间。如果k ~ N，那么枚举它们必须花费O(N^2)时间。

获得O(N)解决方案的唯一方法是添加k为o(sqrt(N))的要求>。一般情况下不可能存在对 k 没有限制的 O(N) 解决方案。

实际的O(k^2)解决方案很简单:

std::string input = ...;

std::vector<size_t> ones;
ones.reserve(input.size());

// O(N) find the 1s
for (size_t idx = 0; idx < input.size(); ++idx) {
    if (input[idx] == '1') {
        ones.push_back(idx);
    }
}

// O(k^2) walk the indices
for (size_t i = 0; i < ones.size(); ++i) {
    for (size_t j = i+1; j < ones.size(); ++j) {
        std::cout << input.substr(i, j - i + 1) << '\n';
    }
}

更新我们必须考虑子字符串的长度以及子字符串的数量。所有字符串的总长度为 O(k * N)，严格大于之前声明的 O(k^2) 界限。因此，在 k 上绑定(bind)的 o(sqrt(N)) 是不够的 - 我们实际上需要 k 为 O(1) 以便产生 O(N) 解决方案。