Reconstruct String from Pi or Z Arrays

This project provides $O(n)$ time constructive algorithms to reconstruct the lexicographically smallest string (over a given alphabet size) from its Prefix Array ($\pi$) or Z-Array. If no such valid string exists, the algorithm mathematically detects the contradictions and rejects the input.

Code Structure

• /Pi/code.cpp: $O(n)$ algorithm for $\pi$-array reconstruction.
• /Z/code.cpp: $O(n)$ algorithm for Z-array reconstruction.
• CheckerPi.cpp & CheckerZ.cpp: Validation checkers.
• ReconstructingString_Slides.pdf: Detailed theory, proofs, and impossible cases.