C++ 更快的字符数组比较

Question

---

我正在尝试做的是找到一种更快的方法来执行相同的程序，但执行速度更快。

#include <cstdio>
#include <cstring>
int main ()
    {
        int br=0, c, n, b, e, i, q, g;
        char t[7000], a[7000];
        scanf("%d" ,&n);
        for (g=0; g<n; g++)  // number of test cases
        {
            scanf ("%7000s",&t);
            c=strlen(t);
            scanf ("%7000s",&a);
            b=strlen(a);
            for (i=0; i<b; i++)  // comparing them
            {
                for (q=0; q<c; q++)
                {
                    if (a[i]==t[q] && a[i]!='' && t[q]!='')
                    {
                    br++;a[i]='';t[q]='';
                    }
                }
            }
            printf("%d n", br);
            br=0;
        }
        return 0;
    }  

<小时 />

程序本身是这样做的：

第一个输入：测试用例数量
2nd：您必须为每个测试用例输入 A 数组和 B 数组
程序必须检查是否有来自 B 的任何常见字母与 A 匹配，如果有，则输出它们的数量。

Example input: 
2
qwerty
abc
abcde
bcex
Output: 
0
3

我需要的是让它运行得更快。任何帮助都值得赞赏。:)

Answer 1

最好对两个字符串中的每个字符进行哈希处理。每个字符对应一个 ASCII 值。将每个字符的计数存储在两个字符串的其他数组中。比较哈希数组。

Answer 2

将您的输入放在两个char排序的容器中，例如 deques。然后执行设置交集并测量结果的大小。这应该会大大降低复杂性

编辑

使用用户输入修正排序的双端面的示例

void addChar2Deque(char newChar, std::deque<char> &sorted_cont) {
    sorted_cont.insert(std::lower_bound(sorted_cont.begin(), sorted_cont.end(), newChar), newChar);
}

如果您只能在预取数据中输入输入，那么您可以对该数据进行排序，例如对于大小为 N 的char数组

std::sort(prefetched_data, prefetched_data+N);

在任何情况下，您最终都会得到两个可以与std::set_intersection进行比较的容器（deque 或 C 数组）

std::vector<char> result;
std::set_intersection(std::begin(cont1), std::end(cont1),
    std::begin(cont2), std::end(cont2), std::back_inserter(result));
return result.size();

Answer 3

为了与带有C++标头的 C 代码的口头禅保持一致，这就是我提到的查找表方法。由此产生的复杂度为 O（N+M），其中 N 和 M 是各自字符串的长度。由于已成定局，每个字符串中的每个字符必须至少访问一次（在这种情况下不超过此），因此我有点放心地建议算法方面，如果不进入 asm bag-o-tricks，就很难做得更好。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
int main()
{
    int n;
    if (scanf("%d", &n) != 1 || n < 0)
        return EXIT_FAILURE;
    while (n-- >0)
    {
        char a[7000], b[7000];
        if (scanf ("%7000s", a) == 1 && scanf ("%7000s", b) == 1)
        {
            unsigned short table[1 << CHAR_BIT] = {0};
            unsigned int answer = 0;
            const char *p;
            for (p=b; *p; ++table[(unsigned char)*p++]);
            for (p=a; *p; ++p)
            {
                if (table[(unsigned char)*p])
                {
                    --table[(unsigned char)*p];
                    ++answer;
                }
            }
            printf("%un", answer);
        }
    }
    return EXIT_SUCCESS;
}