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

以下面的字符串为例:

'快速的棕色狐狸'

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

'速度极快的深棕色狐狸'

现在 q 在索引 9 处,f 在索引 26 处。

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

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

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

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

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

请先 登录 后评论

4 个回答

Kyle Cronin

您的问题有点含糊 - 您是否希望跟踪每个字母的第一个实例?如果是这样,长度为 26 的数组可能是最佳选择。

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

请先 登录 后评论
Unsliced

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

请先 登录 后评论
Community

假设你有一个字符串,它的一些字母是有趣的。为方便起见,假设索引 0 处的字母总是很有趣,并且您从不在它之前添加任何内容

请先 登录 后评论
Rafał Dowgird

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

在这个结构中插入或删除一个字母只需要 O(log(N)) 操作(更新到根路径上的位图),找到第一次出现的字母也需要 O(log(N)) 操作 -你从根开始,寻找位图包含有趣字母的最左边的孩子。

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

请先 登录 后评论