以以下字符串为例：

"快速的棕色狐狸"

现在，快速q中的字符位于字符串的索引4(从0开始)，而f in f中的字符位于索引16. 现在，假设用户在此字符串中输入了更多文本。

"非常快的黑褐色狐狸"

现在，q在索引9处，而f在索引26处。

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

语言对我来说无关紧要，这比任何其他问题都更是理论问题，因此请使用我们想使用的任何语言，仅尝试将其保留为普遍流行和当前的语言。

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

即使在示例中我一直在寻找字符串中唯一字符的索引，我也希望能够跟踪不同位置(例如，棕色的o和狐狸的o)中相同字符的索引。因此搜索是不可能的。

我希望答案是既节省时间又节省内存，但是如果我只选择一个，我会更在意性能速度。

解决方案

回答

问题有点模棱两可，我们要跟踪每个字母的开头吗？如果是这样，长度为26的数组可能是最佳选择。

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

回答

如果我们牢记目标语言，这也将有所帮助，因为并非所有数据结构和交互在所有语言中都同样有效。

回答

假设我们有一个字符串，并且其中的一些字母很有趣。为了使事情变得容易，我们假设索引0处的字母总是很有趣，并且我们永远不要在ita sentinel之前添加任何内容。写下对(有趣的字母，到上一个有趣字母的距离)。如果字符串是" + the the quick quick dark brown Fox"，并且我们对" quick"中的q和对" fox"中的f感兴趣，那么我们将输入：(+，0)，(q，10)，(f，17 )。 (符号+是前哨。)

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

现在，我们可以以对数时间查询和更新此数据结构。

要说我们在字符c的左边添加了n个字符，我们说distance(c)+ = n然后去更新c的所有父项的和。

要问c的索引是多少，可以计算sum(c)+ sum(parent(c))+ sum(parent(parent(c)))+ ...

回答

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

在此结构中插入或者删除字母仅需要O(log(N))个操作(将路径上的位图更新到根)，找到字母的第一个出现也需要我们从根，去寻找最左边的孩子，其位图包含有趣的字母。

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