Parameterized Duplications, example
S=xbxzbzzyby A=(prev(Sr))r=2b02b102b0
O(n+m(t,S)) - m(t,S) is number of matches of length at least t
b2:
S(5,6)=b2 (b210b2$)
S(9,2)=b2 (b2$)
S(2,2)=b2 (b20b210b2$)
A4=A8=A1=2, so all matches can be extended
Previous slide
Next slide
Back to first slide
View graphic version