CODEWITHSUNDEEP
stringalgorithmcharacter
Martin Kersten
Martin Kersten

Reputation: 5523

Important algorithm involving random access to a string?

I am implementing a different string representation where accessing a string in non-sequential manner is very costly. To avoid this I try to implement certain position caches or character blocks so one can jump to certain locations and scan from there.

In order to do so, I need a list of algorithms where scanning a string from right to left or random access of its characters is required, so I have a set of test cases to do some actual benchmarking and to create a model I can use to find a local/global optimum for my efforts.

Basically I know of:

String.charAt
String.lastIndexOf
String.endsWith

One scenario where one needs right to left access of strings is extracting the file extension and the file name (item) of paths.

For random access i find no algorithm at all unless one has prefix tables and access the string more randomly checking all those positions for longer than prefix strings.

Does anyone know other algorithms with either right to left or random access of string characters is required?

[Update] The calculation of the hash-code of a String is calculated using every character and accessed from left to right along the value is stored in a local primary variable. So this is not something for random access.

Also the MD5 or CRC algorithm also all process the complete string. So I do not find any random access examples at all.

Upvotes: 1

Views: 93

Answers (1)

rici
rici

Reputation: 241931

One interesting algorithm is Boyer-Moore searching, which involves both skipping forward by a variable number of characters and comparing backwards. If those two operations are not O(1), then KMP searching becomes more attractive, but BM searching is much faster for long search patterns (except in rare cases where the search pattern contains lots of repetitions of its own prefix). For example, BM shines for patterns which must be matched at word-boundaries.

BM can be implemented for certain variable-length encodings. In particular, it works fine with UTF-8 because misaligned false positives are impossible. With a larger class of variable-length encodings, you might still be able to implement a variant of BM which allows forward skips.

There are a number of algorithms which require the ability to reset the string pointer to a previously encountered point; one example is word-wrapping an input to a specific line length. Those won't be impeded by your encoding provided your API allows for saving a copy of an iterator.

Upvotes: 1

Related Questions