字符串比较的快速方法

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

O(2n) 和 O(n) 完全相同，因为 "O" 表示方法成本的渐近行为。

更新：我刚刚注意到你的意思是 O(n^2) 和你的 O(N2)。

如果您需要进行比较，您的成本将始终为 O(n^2)，因为您必须：

1) Loop 为你单词的每个字符，这是 O(n)

2) 比较每个单词中的当前字符，您将不得不使用一个包含您已经检查过的字符的临时列表。所以，这是另一个嵌套的 O(n).

所以，O(n) * O(n) = O(n^2).

注意：您始终可以忽略 O 表达式中的数字系数，因为它无关紧要。

Answer 2

您可以使用 dynamic programming 实现 O(n)。即使用整数 d 来存储差异。

Algo:
move from lower index to higher index of both array.  
if a[i] not equal b[j]:
           increase d by 2
           move the index of smaller array and check again.
if a[i] is equal to b[j] : 
           decrease d by 1
           move both index
repeat this until reach the end of array

Answer 3

我原本以为您需要一个相当复杂的算法，例如 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。

Answer 4

在看到答案真的很简单之后，感谢@Bill Lynch，我的解决方案可能太复杂了！无论如何，这是一个简单的计数差异。

#include <iostream>
#include <algorithm>
#include <array>

int main() {
    std::array<int,26> str1 = {};
    std::array<int,26> str2 = {};

    std::string s1("abce");
    std::string s2("bccd");


    for(char c : s1)
        ++str1[c-'a'];
    for(char c : s2)
        ++str2[c-'a'];

    int index = 0;

    std::cout << std::count_if(str1.begin(),str1.end(),[&](int x)
    {
        return x != str2[index++];
    });
}

是O(n+m)，除非我分析有误

字符串比较的快速方法

fast way for string comparison

c++

string

string-comparison