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.
class A{public static ...}
everytime I wanted to golf code \$\endgroup\$ – Bassdrop Cumberwubwubwub Jul 4 '16 at 8:59