Re: Analysing a (binary) string. (Solved)

[hexcoder]

Hi,

just for completeness (since its solved). A suitable data structure could be that of a suffix tree or a suffix array. It allows finding the longest repeating substring(s) in linear time.

I found this page instructive: http://www.allisons.org/ll/AlgDS/Tree/Suffix/.

I am using it in the detection of cut-and-paste code.

[BrowserUk]

Two questions:

1. Have you ever built a suffix (or any kind of) tree in Perl with 30 million nodes?
2. What effect do you think the presence of errors in the repeats would have upon the suffix trees ability to detect them?

[hexcoder]

1. Not yet, but a suffix array has lower space requirements than a suffix tree.

2. In Dan Gusfield's book 'Algorithms on Strings, Trees, and Sequences' several inexact matching solutions based on suffix trees are discussed (for example in chapter 12.2). If there are up to k errors without insertions and deletions, it is the k-mismatch problem (see chap. 9.4) with a solution running in O(km), where k is the number of errors and m is the length of the string. Otherwise if the errors shall include insertions/deletions it is called the k-difference problem.

Hope that helps.