c++ - 查找两个字符串共有的最大字符数

Question

找出两个字符串共有的最大字符数。字符区分大小写，即小写和大写字符被认为是不同的。

这是我的代码:

#include <iostream>
#include <cstring> 
using namespace std;

int main() {
    std::string a, b;
    int number_cases = 0, count = 0;
    cin >> number_cases;
    while (number_cases != 0) {
        cin >> a;
        cin >> b;
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                if (a[i] == b[j]) {
                    count++;
                    b[j] = '#';
                    break;
                }
            }
        }
        cout << count << endl;
        count = 0;
        --number_cases;
    }
}

但运行时间超过 1 秒，我需要将其控制在 1 秒以下或恰好 1 秒。有什么优化技巧吗？

Answer 1

只需对它们进行排序并使用 set_intersection

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

int main()
{
    std::string s1 = "Hello";
    std::string s2 = "World";

    std::sort(begin(s1), end(s1));
    std::sort(begin(s2), end(s2));

    std::string s3;
    std::set_intersection(begin(s1), end(s1), begin(s2), end(s2), std::back_inserter(s3));
    std::cout << s3.size() << ":" << s3;
}

Live Example .

注意:如果您对独特的重叠字符感兴趣，可以在s3 上运行std::unique。