Compute the runs of a string

Question

Consider the following definitions taken from The number of runs in a string by W. Rytter. Note that word, string and substring are all roughly synonyms.

A run in a string is a nonextendable (with the same minimal period) periodic segment in a string.

A period p of a word w is any positive integer p such that w[i]=w[i+p] whenever both sides of this equation are defined. Let per(w) denote the size of the smallest period of w . We say that a word w is periodic iff per(w) <= |w|/2.

For, example consider the string x = abcab. per(abcab) = 3 as x[1] = x[1+3] = a, x[2]=x[2+3] = b and there is no smaller period. The string abcab is therefore not periodic. However, the string abab is periodic as per(abab) = 2.

A run (or maximal periodicity) in a string w is an interval [i...j] with j>=i, such that

• w[i...j] is a periodic word with the period p = per(w[i...j])
• It is maximal. Formally, neither w[i-1] = w[i-1+p] nor w[j+1] = w[j+1-p]. Informally, the run cannot be contained in a larger run with the same period.

Denote by RUNS(w) the set of runs of w.

Examples

The four runs of atattatt are [4,5] = tt, [7,8] = tt, [1,4] = atat, [2,8] = tattatt.

The string aabaabaaaacaacac contains the following 7 runs:

[1,2] = aa, [4,5] = aa, [7,10] = aaaa, [12,13] = aa, [13,16] = acac, [1,8] = aabaabaa, [9,15] = aacaaca.

Your output should be a list of runs. Each run should specify the interval it represents but does not need to output the substring itself. The exact formatting can be whatever is convenient for you.

The examples use 1-indexing but you are free to use 0-indexing instead if it is more convenient.

TASK

Write code that given a string w, output RUNS(w).

Languages and input

You can use any language you like and take the input string in whatever form is most convenient. You must give a full program however and you should show an example of your code running on the example input.

Answer 1

Pyth, 38 bytes

{smm,hk+ekdfgaFTdcx1xM.ttB+0qVQ>QdZ2Sl

  m                                 SlQ   map for d in [1, …, len(input)]:
                            qVQ>Qd          pairwise equality of input[:-d] and input[d:]
                        tB+0                duplicate this list, prepending 0 to one copy
                      .t          Z         transpose, padding with 0
                    xM                      pairwise xor
                  x1                        find all occurrences of 1
                 c                 2        chop into groups of 2
           f                                filter for groups T such that:
             aFT                              the absolute difference between its elements
            g   d                             is greater than or equal to d
   m                                        map for groups k:
     hk                                       first element
    ,  +ekd                                   pair with the last element plus d
 s                                        concatenate
}                                         deduplicate

Test suite

Answer 2

CJam, 66

q:A,2m*{~A>_@)_@<2*@@2*<=},{_2$-2>2,.+={+}&}*]{[_1=\)\0=2*)+]}%_&p

Try it online

Brief explanation:

The algorithm works in 4 steps (first 3 of them corresponding with the 3 main blocks you can observe):

1. Find all [length index] pairs that correspond to a duplicated substring (such as aabaabaaaacaacac); these are parts of runs.
2. Concatenate pairs that are part of the same run, i.e. consecutive indices and same length/period.
3. Construct the actual runs, by taking the minimum index and maximum index + 2 * length - 1.
4. At the end, remove the duplicated runs (which are the same interval obtained with a different period)

I'd like to golf it more, so this is all subject to change.