在不适合内存的字符序列中查找最长的唯一字符序列？

Question

假设我们有一大堆字符无法放入内存，我们想要找到最长的字符跨度，使得 none 重复。你会怎么做？我熟悉外部排序的概念，但看不到我们如何将类似的技术应用于这样的问题，因为处理字符序列似乎完全依赖于先前的序列。

Answer 1

从位置 0 开始两个指向文件的指针，前指针和后指针。

然后通过文件推进前指针，同时根据需要推进后指针，以确保后指针和前指针之间的跨度不包含重复字符。这将是在前端指针处结束的唯一字符的最长跨度。

为此，您只需维护一个集合，其中包含前后指针之间的所有字符。如果要前移指针，而你传递的字符已经在集合中，那么必须先将后指针前移，直到去掉重复字符。

您以这种方式遇到的最长字符跨度将是文件中唯一字符的最长跨度。

您可以通过打开同一个文件进行两次读取来实现两个文件指针。或者，您可以只打开一次并使用循环缓冲区来记住前后之间的所有内容。只有 256 个（取决于您的字符类型）唯一字符，因此此缓冲区不必太大。