查找不適合內存的字符序列中最長的唯一字符序列？

Question

假設我們有大量的字符無法適應內存，我們希望找到最長的字符長度，以避免重複。你會如何做到這一點？我熟悉外部排序的概念，但並不瞭解我們如何將類似的技術應用於這樣的問題，因爲看起來處理字符序列完全依賴於以前的序列。

Answer 1

在位置0，前端指針和後端指針處啓動兩個指向文件的指針。

然後將前端指針前進通過文件，並且按照需要前進後退指針，以確保後端指針和前端指針之間的跨度不包含重複字符。這將是結束於前端指針的唯一字符的最長跨度。

爲了做到這一點，您只需維護一個包含後指針和前指針之間的所有字符的集合。如果您想要前移指針，並且您傳遞的字符已經在集合中，那麼您必須首先前移指針，直到刪除重複的字符。

以這種方式遇到的最長字符長度將是文件中唯一字符的最長跨度。

您可以通過打開相同的文件來讀取兩次來實現兩個文件指針。或者，您可以只打開一次，並使用循環緩衝區來記住後臺和前臺之間的所有內容。只有256個（取決於你的字符類型）獨特的字符，所以這個緩衝區不必太大。