规则: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字符,可能很多。 因此,为了找出a和b中出现非ASCII字符的次数,我应该使用哈希表来存储它们的出现时间吗? 以字符串a为例:
[non-ASCII's hash-value]:[times]中's hash-val : 2日's hash-val : 1本's hash-val : 1
检查字符串b,如果我们在b中遇到非ASCII字符,然后哈希它并检查一个哈希表,如果字符串存在于哈希表中,那么它的出现次数会减少1.如果出现次数小于0(-1),那么我们说b与a不相似。
或者有更好的方法吗?
PS:我逐字节读取字符串,如果字节小于128,那么我将其作为ASCII字符,否则我将其作为非ASCII字符(多字节)的一部分。 我正在做的是找出非ASCII字符。 这样对吗?
你问过两个问题:
面试官可能正在寻找你说的话,“嗯,如果这些字符串实际上是无法记忆的大量文件,我该怎么办?” 或者你问“好的字符串是否排序?因为如果它们是,我可以更快地做到……”。
但现在让我们说这些字符串很大。 您在内存中存储的唯一内容是哈希表。 Unicode只有大约100万个代码点,并且你为每个代码点存储一个整数计数,所以即使你从千兆字节大小的文件中获取数据,你的哈希表只需要大约4MB左右(或者是这个的一小部分,因为它会在头顶上)。
在没有任何其他条件的情况下,您的算法很好。 事先对字符串进行排序并不好; 它占用更多内存,而不是线性时间操作。
附录
由于你的原始注释提到了char
类型而不是wchar_t
,我想我会展示一个使用宽字符串的例子。 见https://codepad.org/B3MXOgqc
希望有所帮助。
附录2
好的,这是一个C程序,它显示了如何通过宽字符串并在角色级别工作:
这是一个非常短的程序,所以我也将它贴在这里:
#include #include #include char *s1 = "abd中日"; wchar_t *s2 = L"abd中日"; int main() { int i, n; printf("length of s1 is %dn", strlen(s1)); printf("length of s2 using wcslen is %dn", wcslen(s2)); printf("The codepoints of the characters of s2 aren"); for (i = 0, n = wcslen(s2); i < n; i++) { printf("%02xn", 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
我们可以从中学到什么? 几件事:
在这个例子中,我定义了一个带有CJK字符的字符串,并使用了wchar_t
和一个带有wcslen
的for循环。 请注意,我正在使用真实字符,而不是BYTES,所以我得到了正确的字符数,即5.现在我打印出每个代码点。 在你的面试问题中,你将看到代码点是否>=
128.我用Hex显示它们,就像文化一样,所以你可以寻找>
0x7F。 ?
附录3
字符处理比上面的简单示例要多得多。 在下面的评论中,JF Sebastian提供了许多其他重要的链接。
需要解决的几个问题是规范化。 例如,你的面试官是否关心当给出两个字符串时,一个只包含一个Ç而另一个包含一个C后跟一个COMBINING MARK CEDILLA BELOW,它们是否相同? 它们代表相同的字符 ,但是一个使用一个代码点,另一个使用两个。
以上就是c/c++开发分享找出2个相似或不相似的字符串相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/559579.html