string - 涉及随机访问字符串的重要算法？

Question

我正在实现一种不同的字符串表示形式，其中以非顺序方式访问字符串的成本非常高。为了避免这种情况，我尝试实现某些位置缓存或字符 block ，以便可以跳转到某些位置并从那里扫描。

为此，我需要一个算法列表，其中需要从右到左扫描字符串或随机访问其字符，因此我有一组测试用例来进行一些实际的基准测试并创建一个模型我可以用来为我的努力找到局部/全局最优。

基本上我知道的是:

String.charAt
String.lastIndexOf
String.endsWith

需要从右到左访问字符串的一种情况是提取路径的文件扩展名和文件名(项)。

对于随机访问，我发现根本没有算法，除非有前缀表并更随机地访问字符串，检查所有这些位置是否比前缀字符串长。

有谁知道需要从右到左或随机访问字符串字符的其他算法？

[更新]String 的哈希码的计算是使用每个字符计算的，并沿着值从左到右访问，该值存储在本地主变量中。所以这不是随机访问的东西。

另外MD5或CRC算法也都是处理完整的字符串。所以我根本没有找到任何随机访问的例子。

Answer 1

一个有趣的算法是 Boyer-Moore搜索，包括向前跳过可变数量的字符和向后比较。如果这两个操作不是 O(1)，那么 KMP 搜索变得更有吸引力，但 BM 搜索对于长搜索模式要快得多(搜索模式包含其自身前缀的大量重复的极少数情况除外)。例如，BM 对必须在单词边界处匹配的模式大放异彩。

BM 可以针对某些可变长度编码实现。特别是，它可以很好地与 UTF-8 配合使用，因为不对齐的误报是不可能的。使用更大类的可变长度编码，您可能仍然能够实现 BM 的变体，它允许向前跳过。

有许多算法需要能够将字符串指针重置为先前遇到的点；一个例子是将输入字换行到特定的行长度。如果您的 API 允许保存迭代器的副本，那么您的编码不会阻碍这些。