The proof doesn't mention why the chosen strategy for shrinking t is correct.
Indeed, the naive approach of just scanning the string back from the longest prefix would yield the correct prefix, and indeed the approach in the presented algorithm will find some prefix, but it's not obvious why it will find the longest one.
The proof doesn't mention why the chosen strategy for shrinking t is correct.
Indeed, the naive approach of just scanning the string back from the longest prefix would yield the correct prefix, and indeed the approach in the presented algorithm will find some prefix, but it's not obvious why it will find the longest one.