涉及隨機訪問字符串的重要算法？

Question

我正在實現一個不同的字符串表示形式，其中以非順序方式訪問字符串的代價非常高。爲了避免這種情況，我嘗試實現某些位置緩存或字符塊，以便可以跳到某些位置並從那裏掃描。

爲了做到這一點，我需要一個從右到左掃描字符串或隨機訪問其字符的算法列表，因此我有一組測試用例來做一些實際的基準測試並創建一個模型我可以用來找到一個本地/全球最適合我的努力。

基本上我知道的：

String.charAt 
String.lastIndexOf 
String.endsWith 

一種情況，其中一個需要從右到字符串的左側訪問解壓文件擴展名和路徑的文件名（項）。

對於隨機訪問，我根本找不到任何算法，除非有一個前綴表，並且訪問該字符串比隨機檢查所有這些位置的時間長於前綴字符串。

有沒有人知道其他算法要麼從右到左或隨機訪問字符串是必需的？

[更新] 使用每個字符計算一個字符串的哈希碼，並沿着該值從左到右訪問該值，並將其存儲在本地主變量中。所以這不是隨機訪問的東西。

此外，MD5或CRC算法也處理完整的字符串。所以我根本沒有找到任何隨機訪問的例子。

Answer 1

一個有趣的算法是Boyer-Moore搜索，其中包括向前跳過可變數量的字符和向後比較。如果這兩個操作不是O（1），那麼KMP搜索變得更有吸引力，但是對於長搜索模式（除了在其中搜索模式包含它自己的前綴的許多重複的罕見情況下），BM搜索更快。例如，BM閃耀着必須在單詞邊界處匹配的模式。

BM可以用於某些可變長度編碼。特別是，UTF-8可以正常工作，因爲錯誤的誤報是不可能的。使用更大類的可變長度編碼，您可能仍然能夠實現允許向前跳過的BM的變體。

有一些算法需要能夠將字符串指針重置爲先前遇到的點;一個例子是將輸入封裝爲特定的行長度。如果您的API允許保存迭代器的副本，那麼這些不會受到您編碼的阻礙。