c++ - 查找文件中包含其本身及其反转的单词

Question

这是一个场景，您试图在一个大型文本文件中查找所有单词，而该文件的还原也在该文件中。

所谓“反转”，我的意思是给一个单词“abc”，看看文件中是否有“cba”。文本文件包含大约 10,000,000 个单词。单词长度不超过1000。

我想出的想法是找到一个散列来映射一个词并将其还原为同一个键。并排序尊重关键。所以现在您可以线性检查以找到所有可能符合条件的单词。

问题是:“Find this hash”。欢迎使用任何其他解决此问题的棘手方法。

如果我能找到一个散列来将字符串映射到一个键，我就可以使用外部排序对它们进行排序并使字符串及其反转相邻。所以找到它们很简单。

Answer 1

最简单的哈希是:任意哈希(提供足够大的哈希空间)!

假设您的字符串是“foo”。它的反面是“oof”。在某些任意顺序(例如字典顺序)中，“foo”出现在“oof”之前。现在散列按顺序首先出现的字符串。

所以代替

hash = fancyHash(string);

你会

std::string rstring(string.rbegin(), string.rend());
hash = (string < rstring) ? anyhash(string) : anyhash(rstring);

---

@HighPerformanceMark 建议的一种使用 linux 工具的方法:(text 是一个包含你的话的文件。它们可能在同一行，没关系)

rev text | tr "[:upper:]" "[:lower:]" | tr " " "\n" > rtext; rev rtext > rrtext; comm -12 <(sort -u rrtext) <(sort -u rtext);

解释:

rev反转文件，因此 rev text输出反向 tr "[:upper:]" "[:lower:]"将所有内容转换为小写(可选。如果“Foo”不算作“oOf”的反转，则不要这样做) tr " " "\n"给每个单词一个单独的文件

在此之后，文件 rtext在不同的行上包含小写(可选)单词。此文件中的每个单词都是文件 text 的反向单词.

rev rtext > rrtext再次反转一个以将小写字母也变成原始字母，并将每个单词分隔在不同的行上。

comm -12 <(sort -u rrtext) <(sort -u rtext) .作为 comm 的输入，我们给出了我们首先排序和重复的两个文本文件(-u)。选项 -12抑制第一个输入 ( rrtext ) 或第二个输入 ( rtext ) 唯一的所有单词。因此，此命令的每个输出都存在于两个文件中。