Tuesday, February 9, 2016

String Algorithms

Sorting
  1. Key indexed counting
  2. LSD (Least-significant-digit-first) string sorting
    • Sorts equal length strings.
    • uses key index counting method.
  3. MSD (Most-significant-digit-first) string sorting
    • Recurvise sort
    • Sorst any length strings
  4. 3-way radix sort
String Search
  1. R-way Tries
Sub String Searching
  1. Knuth–Morris–Pratt ( Ref YouTube, GitHub )
    • Runtime complexity - O(m + n) where m is length of text and n is length of pattern
    • Space complexity - O(n)
  2. Boyer–Moore
  3. Robin–Karp

No comments:

Post a Comment