string-algorithms
string-algorithms copied to clipboard
krzysztof-turowski
Collection of string algorithms
Example publications for LCS: - [ ] Apostolico, Guerra - The longest common subsequence problem revisited - [ ] Apostolico, Browne, Guerra - Fast linear-space computations of longest common subsequences...
Approximate string matching with respect to the edit distance: - [ ] Galil, Giancarlo - Improved String Matching with k Mismatches - requires also computation LCP(i, j) in $O(1)$ time...
Example publications for suffix tree: - [ ] Breslauer, Italiano - Near real-time suffix tree construction via the fringe marked ancestor problem - [ ] Giegerich, Kurtz, Stoye - Efficient...
- [ ] Sweedyk - A 2 1/2-approximation algorithm for shortest superstring - 5/2-approximation - [ ] Kaplan, Shafrir - The greedy algorithm for shortest superstrings - 5/2-approximation - [...
- [ ] Fischer - Inducing the LCP-Array - [ ] Gog, Ohlebusch - Compressed Suffix Trees: Efficient Computation and Storage of LCP-Values (conference version: Fast and Lightweight LCP-Array Construction...
- [ ] Hancart - On Simon's string searching algorithm (Simon-Hancart algorithm) - [ ] Breslauer, Galil - Efficient comparison based string matching - [ ] Colussi - Correctness and...
Example publications: - [x] LZ-index from Navarro - Indexing text using the Ziv-Lempel trie, - [x] FM-index from Ferragina, Manzini - Opportunistic data structures with applications, - [ ] succint...
Overall, the aim is to implement several BTW and IBWT transformation algorithms, and to compare them in terms of efficiency (number of accesses of characters) and running time. Selected relevant...
Overall, the aim is to implement several LZ77/78 decomposition algorithms and their reverse methods, and to compare them in terms of efficiency (number of accesses of characters) and running time....