scratch
§ Uses of Minimal String Rotation
created 2021-08-25
- This algorithm always struck me as useless. Now I know some uses.
- 1. Finger print identification: We can encode the finger print into many detailed circular strings. How to search such finger print again from those in very huge data base ? Circular comparision using lyndon factorization is requried.
- 2. Forest canonicalization. Write a tree out in terms of dyck grammar / brackets. Forest will correspond to sequence of such trees. When are two forests equivalent? Normalize them by minimal rotation.
❦