P-Trees & Suffix Links
Baker: Why do suffix links work?
- Common Prefix Property: if aS=bT then S=T
- Distinct Right Context: if aS=bT and aSc ? bTd then Sc?Td
Distinct Right Context does not hold for p-strings
S=xabxyabz
prev(xabx)=0ab3 prev(yabz)=0ab0
0ab=0ab (aS=bT)
prev(xabx) ? prev(yabz) (aSc ? bTd)
prev(abx)=ab0=prev(abz) (Sc=Td)
xabx - repetition of parameter