[This question is a follow up to Compute the runs of a string ]
pof a string
wis any positive integer
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 string
wis periodic iff
per(w) <= |w|/2.
So informally a periodic string is just a string that is made up from another string repeated at least once. The only complication is that at the end of the string we don't require a full copy of the repeated string as long as it is repeated in its entirety at least once.
For, example consider the string
x = abcab.
per(abcab) = 3 as
x = x[1+3] = a,
x=x[2+3] = b and there is no smaller period. The string
abcab is therefore not periodic. However, the string
ababa is periodic as
per(ababa) = 2.
As more examples,
abcabcabc are also periodic.
For those who like regexes, this one detects if a string is periodic or not:
The task is to find all maximal periodic substrings in a longer string. These are sometimes called runs in the literature.
wis a maximal periodic substring (run) if it is periodic and 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.
Because two runs can represent the same string of characters occurring in different places in the overall string, we will represent runs by intervals. Here is the above definition repeated in terms of intervals.
A run (or maximal periodic substring) in a string
Tis an interval
j>=i, such that
T[i...j]is a periodic word with the period
p = per(T[i...j])
- It is maximal. Formally, neither
T[i-1] = T[i-1+p]nor
T[j+1] = T[j+1-p]. Informally, the run cannot be contained in a larger run with the same period.
RUNS(T) the set of runs in string
Examples of runs
The four maximal periodic substrings (runs) in string
T = atattattare
T[4,5] = tt,
T[7,8] = tt,
T[1,4] = atat,
T[2,8] = tattatt.
T = aabaabaaaacaacaccontains the following 7 maximal periodic substrings (runs):
T[1,2] = aa,
T[4,5] = aa,
T[7,10] = aaaa,
T[12,13] = aa,
T[13,16] = acac,
T[1,8] = aabaabaa,
T[9,15] = aacaaca.
T = atatbatatbcontains the following three runs. They are:
T[1, 4] = atat,
T[6, 9] = atatand
T[1, 10] = atatbatatb.
Here I am using 1-indexing.
Write code so that for each integer n starting at 2, you output the largest numbers of runs contained in any binary string of length
Your score is the highest
n you reach in 120 seconds such that for all
k <= n, no one else has posted a higher correct answer than you. Clearly if you have all optimum answers then you will get the score for the highest
n you post. However, even if your answer is not the optimum, you can still get the score if no one else can beat it.
Languages and libraries
You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.
In the following:
n, optimum number of runs, example string.
2 1 00 3 1 000 4 2 0011 5 2 00011 6 3 001001 7 4 0010011 8 5 00110011 9 5 000110011 10 6 0010011001 11 7 00100110011 12 8 001001100100 13 8 0001001100100 14 10 00100110010011 15 10 000100110010011 16 11 0010011001001100 17 12 00100101101001011 18 13 001001100100110011 19 14 0010011001001100100 20 15 00101001011010010100 21 15 000101001011010010100 22 16 0010010100101101001011
What exactly should my code output?
n your code should output a single string and the number of runs it contains.
My Machine The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code.
- 49 by Anders Kaseorg in C. Single threaded and run with L = 12 (2GB of RAM).
- 27 by cdlane in C.