Maybe I just need some coffee, but GrandFathers algorithm generates the list of all maximum patterns including the sequence ids. In your example, the hash would contain something like

$matches{$pattern} = [ [1,3], ... [ 5, 6 ], ];
[download]

after sum(1..n-1) comparsions. Isn't that what kdt2006 asked for?