11
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ Nice challenge, but is there a good reason to overrule the default and disallow functions? \$\endgroup\$ – Martin Ender Jul 4 '16 at 8:53
  • \$\begingroup\$ @MartinEnder It's just my preference. It makes it easier for people to just copy and paste code and try it out themselves which in turn makes the answers more interesting for more people. \$\endgroup\$ – user9206 Jul 4 '16 at 8:56
  • 4
    \$\begingroup\$ But that also causes a lot of overhead code, which makes the competition unfair for languages with a verbose syntax. I wouldn't be golfing in Java for example if I had to write class A{public static ...} everytime I wanted to golf code \$\endgroup\$ – Bassdrop Cumberwubwubwub Jul 4 '16 at 8:59
  • \$\begingroup\$ @BassdropCumberwubwubwub I can see there are pros and cons. I happen to weigh the pros more strongly. I think it's most interesting to compare the length of golf'ed answers in similar languages in any case rather than comparing APL to Python for example. \$\endgroup\$ – user9206 Jul 4 '16 at 9:05
  • \$\begingroup\$ "a run is maximal if it is not fully contained within any larger run" but in your first example, [7,8] is fully contained within [2,8]. Or are you strictly talking about runs that repeat the same substring? \$\endgroup\$ – aditsu Jul 4 '16 at 16:45
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I get "[[3, 5], [6, 8], [0, 4], [1, 8]]" from "atattatt". Does [3,5] represent "tt"? It would be great if you could explain the algorithm you have used as well at a high level. \$\endgroup\$ – user9206 Jul 5 '16 at 7:54
  • \$\begingroup\$ @Lembik Yes, [i, j] represents the slice starting between (0-indexed) characters i-1 and i and ending between characters j-1 and j. This is the standard convention in Pyth and most sane languages, as it should be (see here and here). \$\endgroup\$ – Anders Kaseorg Jul 5 '16 at 9:22
  • \$\begingroup\$ Great. Is it possible to describe your solution intuitively? I can't reverse engineer it from your code description unfortunately. \$\endgroup\$ – user9206 Jul 5 '16 at 9:25
  • 1
    \$\begingroup\$ @Lembik Suppose we are looking for runs of period d. We find all the locations where character i matches character i + d. We then find runs of at least d consecutive such locations. Repeat for all d. We have to deduplicate at the end because the real period might have only been a divisor of d. \$\endgroup\$ – Anders Kaseorg Jul 5 '16 at 9:32
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for this. Could you explain the algorithm you have used too please? \$\endgroup\$ – user9206 Jul 5 '16 at 7:55
  • 1
    \$\begingroup\$ @Lembik ok, updated \$\endgroup\$ – aditsu Jul 5 '16 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy