c++ - 字符串比较的快速方法

Question

我有一个简单的问题，但它让我感到困惑。

我有两个字符串，我想计算两个字符串之间有多少个不同的字符。字符串已排序，长度相等。不要拆分字符串。

例如

input:  abc, bcd
output: 2, because a and d are different characters

input:  abce, bccd
output: 4, because a, c, d and e are different.

我知道我可以在 O(N^2) 的时间内完成，但我如何才能在 O(N) 的时间内解决这些已排序的字符串？

只需要不同字符的个数，不需要指明是哪个个数。

Answer 1

我原本以为你需要一个相当复杂的算法，比如 Smith-Waterman例如。但是对输入的限制使得在 O(m + n) 中实现这一点相当容易，其中 m 是第一个字符串的长度，而 n 是第二个字符串的长度。

我们可以使用内置算法来计算相同字符的数量，然后我们可以使用该信息生成您要查找的数字:

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

int main() {
    std::string m = "abce";
    std::string n = "bccd";
    std::string result;

    std::set_intersection(
            m.begin(), m.end(),
            n.begin(), n.end(),
            std::back_inserter(result));

    std::cout << m.size() + n.size() - 2 * result.size() << "\n";
}

在这种特殊情况下，它会根据需要输出 4。