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

Question

以下面的字符串为例:

“敏捷的棕色狐狸”

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

“非常敏捷的深棕色狐狸”

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

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

语言对我来说无关紧要，这更像是一个理论问题，所以使用任何你想要的语言，尽量使用普遍流行和流行的语言。

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

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

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

Answer 1

假设您有一个字符串，其中的一些字母很有趣。为了让事情更简单，我们假设索引 0 处的字母总是有趣的，并且您永远不会在它之前添加任何东西——一个哨兵。写下成对的(有趣的字母，与前一个有趣字母的距离)。如果字符串是“+the very Quick dark brown Fox”并且你对'quick'中的q和'fox'中的f感兴趣那么你会写:(+，0)，(q，10)，(f，17 ). (符号 + 是哨兵。)

现在你把它们放在一个平衡的二叉树中，它的中序遍历按照它们在字符串中出现的顺序给出字母序列。您现在可能会认出 partial sums problem :您增强树，使节点包含(字母、距离、总和)。总和是左子树中所有距离的总和。 (因此 sum(x)=distance(left(x))+sum(left(x))。)

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

要说你在字符 c 的左边添加了 n 个字符，你说 distance(c)+=n 然后去更新 n 的所有父级的总和em>c.

要问 c 的索引是什么，你计算 sum(c)+sum(parent(c))+sum(parent(parent(c)))+...