跟踪字符串中特定字符的索引的最有效方法是什么？

Question

以下面的字符串为例：

“敏捷的棕色狐狸”

现在，quick 中的 q 位于字符串的索引 4 处（从 0 开始），fox 中的 f 位于索引 16 处。现在假设用户在该字符串中输入更多文本。

“速度非常快的深棕色狐狸”

现在 q 位于索引 9 处，f 位于索引 26 处。

无论用户添加了多少个字符，跟踪 Quick 中原始 q 和 Fox 中原始 f 的索引的最有效方法是什么？

语言对我来说并不重要，这更多的是一个理论问题，所以使用你想要的任何语言只是尽量保持它为普遍流行和当前的语言。

我给出的示例字符串很短，但我希望有一种方法可以有效地处理任何大小的字符串。因此，使用偏移量更新数组可以使用短字符串，但会陷入许多字符的困境。

尽管在示例中我正在寻找字符串中唯一字符的索引，但我也希望能够跟踪不同位置中同一字符的索引，例如 Brown 中的 o 和 Fox 中的 o。所以寻找是不可能的。

我希望答案既节省时间又节省内存，但如果我必须选择一个，我更关心性能速度。

Answer 1

假设您有一个字符串，其中的一些字母是 有趣的. 。为了让事情变得更简单，我们假设索引 0 处的字母总是有趣的，并且您从不在它前面添加一些东西 - 哨兵。写下成对的（有趣的字母，到前一个有趣的字母的距离）。如果字符串是“+theveryQuickdarkbrownFox”并且您对“quick”中的 q 和“fox”中的 f 感兴趣，那么您可以这样写：(+,0)、(q,10)、(f,17)。（+号是哨兵。）

现在，您将它们放入平衡二叉树中，该树的有序遍历按照字母在字符串中出现的顺序给出字母序列。您现在可能认识到 部分和问题: ：您增强树，使节点包含（字母、距离、总和）。总和是左子树中所有距离的总和。（因此 sum(x)=距离(left(x))+sum(left(x))。）

您现在可以在对数时间内查询和更新此数据结构。

说你添加了 n 字符左侧的字符 C 你说 distance(c)+=n 然后去更新所有父母的总和 C.

询问索引是什么 C 您计算 sum(c)+sum(parent(c))+sum(parent(parent(c)))+...

Answer 2

你的问题有点模棱两可——你想要跟踪每个字母的第一个实例吗？如果是这样，长度为 26 的数组可能是最佳选择。

每当您将文本插入字符串中低于索引的位置时，只需根据插入字符串的长度计算偏移量即可。

Answer 3

如果您心中有一种目标语言，这也会有所帮助，因为并非所有数据结构和交互在所有语言中都同样有效。

Answer 4

在类似情况下通常有用的标准技巧是将字符串的字符保留为平衡二叉树中的叶子。此外，树的内部节点应该保留以特定节点为根的子树中出现的字母集（如果字母表很小且固定，它们可以是位图）。

在该结构中插入或删除字母只需要 O(log(N)) 操作（更新根路径上的位图），并且查找字母的第一次出现也需要 O(log(N)) 操作 - 您从根，寻找位图包含有趣字母的最左边的孩子。

编辑：内部节点还应保留所表示子树中的叶子数量，以便有效计算字母索引。