string - 如何在线性时间内获取字符串元素之间的顺序关系？

Question

我有一个字符串，我想在线性时间内获取字符串元素之间的顺序关系。

比如字符串“abc”，有3个偏序关系，分别是ab、bc、ac

Answer 1

如果您想生成所有有序对 - 那么其中有 n^2 个，因此您甚至无法在线性时间内打印它们。

但是，如果您只需要能够为一些更大的算法查找两个字符的顺序（并且它们在原始字符串中都是唯一的）：您可以在一次传递中构建一个字符映射到它们在字符串中的索引（线性时间）。然后，每当您需要知道给定对的顺序时，请在恒定时间内查找并比较它们的索引。