c - 找出2个相似或不相似的字符串

Question

规则:2 个字符串，a 和 b，它们都由 ASCII 字符和非 ASCII 字符(例如，汉字 gbk 编码)组成。

If the non-ASCII chars contained in b also show up in a and no less than the times they appear in b, then we say b is similar with a.

例如:

a = "ab中ef日jkl中本"  //non-ASCII chars:'中'(twice), '日'(once), '本'(once)
b = "bej中中日"  //non-ASCII chars:'中'(twice), '日'(once)
c = 'lk日日日'   //non-ASCII chars:'日'(3 times, more than twice in a)

根据规则，b 与 a 相似，但 c 不相似。这是我的问题:我们不知道 a 和 b 中有多少非 ASCII 字符，可能很多。因此，要找出非 ASCII 字符在 a 和 b 中出现了多少次，我是否应该使用哈希表来存储它们的出现时间？以字符串a为例:

[non-ASCII's hash-value]:[times]
     中's hash-val      : 2
     日's hash-val      : 1
     本's hash-val      : 1

检查字符串 b，如果我们在 b 中遇到非 ASCII 字符，则对其进行哈希处理并检查 a 的哈希表，如果该字符存在于 a 的哈希表中，则其出现次数减 1。如果出现次数小于 0(-1)，则我们说 b 与 a 不相似。

或者有什么更好的方法吗？

附言:我是一个字节一个字节地读取字符串，如果字节小于128，那么我就把它当作一个ASCII字符，否则我就把它当作一个非ASCII字符(多字节)的一部分。这就是我为找出非 ASCII 字符所做的工作。对吗？

Answer 1

你问了两个问题:

1. 我们可以使用哈希表计算非 ASCII 字符吗？答:当然可以。当您读取字符(不是字节)时，检查代码点。对于大于 127 的任何代码点，将其放入计数哈希表中。即对于字符 c，如果 c 不在表中，则添加 (c,1)，如果 c 已经在表中，则将 (c,x) 更新为 (c, x+1)。

   <

2. 有没有比在 a 中递增计数并在运行 b 时递减计数的方法更好的解决此问题的方法？如果您的哈希表实现提供接近 O(1) 的访问权限，那么我怀疑不会。您正在查看字符串中的每个字符一次，并且对于每个字符，您正在执行哈希表插入或查找以及加法或减法，以及针对 0 的检查。对于未排序的字符串，您有无论如何都要查看两个字符串中的所有字符，所以我认为您已经给出了最佳解决方案。

面试官可能希望你说这样的话，“嗯嗯，如果这些字符串实际上是内存无法容纳的大量文件，我该怎么办？”或者你问“字符串排序了吗？因为如果排序了，我可以做得更快......”。

但现在假设字符串很大。您唯一存储在内存中的是哈希表。 Unicode 只有大约 100 万个代码点，并且您要为每个代码点存储一个整数计数，因此即使您从千兆字节大小的文件中获取数据，您的哈希表也只需要大约 4MB 左右(或者它的一小部分，因为开销)。

在没有任何其他条件的情况下，您的算法很好。事先对字符串进行排序并不好；它占用更多内存并且不是线性时间操作。

附录

由于您最初的评论提到了 char 类型而不是 wchar_t，我想我应该展示一个使用宽字符串的示例。参见 http://codepad.org/B3MXOgqc

希望对您有所帮助。

附录 2

好的，这是一个 C 程序，它准确地展示了如何遍历宽字符串并在字符级别工作:

http://codepad.org/QVX3QPat

这是一个非常短的程序，所以我也将它粘贴在这里:

#include <stdio.h>
#include <string.h>
#include <wchar.h>

char *s1 = "abd中日";
wchar_t *s2 = L"abd中日";

int main() {
    int i, n;
    printf("length of s1 is %d\n", strlen(s1));
    printf("length of s2 using wcslen is %d\n", wcslen(s2));
    printf("The codepoints of the characters of s2 are\n");
    for (i = 0, n = wcslen(s2); i < n; i++) {
        printf("%02x\n", s2[i]);
    } 
    return 0;
}

输出:

length of s1 is 9
length of s2 using wcslen is 5
The codepoints of the characters of s2 are
61
62 
64
4e2d
65e5

我们可以从中学到什么？几件事:

1. 如果您对 CJK 字符使用普通的旧 char，则字符串长度将是错误的。
2. 要在 C 中使用 Unicode 字符，请使用 wchar_t
3. 对于宽字符串，字符串文字有一个前导 L

在这个例子中，我定义了一个带有 CJK 字符的字符串，并使用了 wchar_t 和一个带有 wcslen 的 for 循环。请注意，我使用的是真实字符，而不是 BYTES，因此我得到了正确的字符数，即 5。现在我打印出每个代码点。在您的面试问题中，您将查看代码点是否为 >= 128。我以十六进制显示它们，文化也是如此，因此您可以查找 >= 0x7F。 :-)

附录 3

http://tldp.org/HOWTO/Unicode-HOWTO-6.html 中的一些注意事项值得一读。字符处理比上面的简单示例显示的要多得多。在下面的评论中，J.F. Sebastian 提供了许多其他重要链接。

需要解决的少数事情是规范化。例如，您的面试官是否关心当给定两个字符串时，一个仅包含一个 Ç，另一个包含一个 C，后跟一个 COMBINING MARK CEDILLA BELOW，它们是否相同？它们代表相同的字符，但一个使用一个代码点，另一个使用两个。