23
\$\begingroup\$

Given a string as argument, output the length of the longest(s) non-overlapping repeated substring(s) or zero if there is no such string.

You can assume the input string is not empty.

Examples

abcdefabc : the substring abc is repeated at positions 1 and 7, so the program should output 3

abcabcabcabcab : abcabc or bcabca or cabcab are repeated, so the program should output 6. (the substring abcabcabcab is also repeated, but the occurrences overlap, so we don't accept it).

aaaaaaa : aaa is repeated at positions 1 and 4 for example, so the program should output 3

abcda : a is repeated, so the program should output 1

xyz : no repeated string → 0

ababcabcabcabcab : should return 6

This is , so fewest bytes wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Could the string be empty? If that's the case, would it be allowed to output False rather than 0? \$\endgroup\$ – Dennis Dec 17 '16 at 5:52
  • \$\begingroup\$ @Dennis You can assume the string is not empty. \$\endgroup\$ – Arnaud Dec 18 '16 at 1:35

15 Answers 15

9
\$\begingroup\$

brainfuck, 226 bytes

,[<<<,]+[>>->[[[[>>[>>>]<+<-<[<<<]>>+<-]>[<+>-]>[>>>]<<[>[<+>-]]>[[<+>-]>+[<<<]>
>>-[+>[<<<]<[>+>[->]<<[<]>-]>[<+>>+<-]>>>[>>>]]>>]<]>+[,<<<+]->[<<<]>>>>>+[,+>>>
+]-[>>>]->]<[+<<<]+<<<++[->>>]+>>>->]<[,<<<]<[>>>+<<<-]>+>,>>>]<<.

Formatted:

,[<<<,]
+
[
  for each suffix
  >>->
  [
    for each prefix
    [
      for each suffix
      [
        for each char while no mismatch
        [
          >>[>>>]
          <+<-<[<<<]
          > >+<-
        ]
        >[<+>-]
        >[>>>]
        <<
        [
          mismatch
          >[<+>-]
        ]
        >
        [
          [<+>-]
          >+[<<<]
          >>>-
          [
            match
            +>[<<<]
            <
            [
              >+>[->]
              <<[<]
              >-
            ]
            >[<+> >+<-]
            >>>[>>>]
          ]
          >>
        ]
        <
      ]
      >+[,<<<+]
      ->[<<<]
      >>> >>+[,+>>>+]
      -[>>>]
      ->
    ]
    <[+<<<]
    +<<<++[->>>]
    +>>>->
  ]
  <[,<<<]
  <[>>>+<<<-]
  >+>,>>>
]
<<.

Expects input with or without a trailing newline, and outputs the result as a byte value.

Try it online.

This checks each prefix to see whether it occurs later in the string, then chops off the first character and repeats the process until there are no more characters left.

The tape is divided into 3-cell nodes,

c 0 f

where c is a character of the given string, and f is a flag that can be either one, negative one, or zero. Nonzero flags are placed between the two characters currently being compared, and negative ones are reserved for the cells after the end of the current prefix and before the beginning of the current suffix (i.e., before the index of the current potential match).

The result is stored to the left of the string and is updated whenever a match is found.

(The string is actually processed in reverse with a \x01 appended to it.)

\$\endgroup\$
6
\$\begingroup\$

Jelly, 12 bytes

œ-QL€
ŒṖÇ€FṀ

Try it online!

How it works

ŒṖÇ€FṀ  Main link. Argument: s (string)

ŒṖ      Generate all partitions of s.
  ǀ    Apply the helper link to each partition.
    F   Flatten the resulting array of lengths.
     Ṁ  Take the maximum.


œ-QL€   Helper link. Argument: P (partition)

  Q     Yield the elements of P, deduplicated.
œ-      Multiset subtraction; remove exactly one occurrence of each string in P.
   L€   Compute the lengths of the remaining strings. 
\$\endgroup\$
  • 1
    \$\begingroup\$ All hail Jelly, the ultimate code golf language! \$\endgroup\$ – Nissa Dec 17 '16 at 17:01
  • \$\begingroup\$ œ-Q is really neat. \$\endgroup\$ – Lynn Dec 18 '16 at 17:16
5
\$\begingroup\$

Perl 6, 36 bytes

{m:ex/(.*).*$0/.map(*[0].chars).max}

Try it

Expanded:

{   # bare block lambda with implicit parameter 「$_」

  m           # match ( implicitly against 「$_」
  :exhaustive # every possible way
  /
    (.*)      # any number of characters ( stored in 「$0」 )
    .*
    $0
  /

  .map(

    *\        # the parameter to Whatever lambda
    [0]\      # the value that was in 「$0」 for that match
    .chars    # the number of characters

  ).max

}
\$\endgroup\$
5
\$\begingroup\$

Retina, 35 32 30 bytes

Pretty cool challenge.

M&!`(.*)(?=.*\1)
M%`.
O#^`
G1`

Try it online

Explanation:

M&!`(.*)(?=.*\1)    # Prints overlapping greedy substrings occuring more than once
M%`.                # Replace each line with its length
O#^`                # Sort lines by number in reverse
G1`                 # Return the first line
\$\endgroup\$
  • \$\begingroup\$ You can save two bytes by using M%`. as the second stage. \$\endgroup\$ – Martin Ender Dec 17 '16 at 8:31
4
\$\begingroup\$

JavaScript (ES6), 79 68 66 bytes

f=(s,r,l=s.match(/(.*).*\1/)[1].length)=>s?f(s.slice(1),l<r?r:l):r
<input oninput=o.textContent=f(this.value)><pre id=o>

Edit: Saved 11 13 bytes thanks to @Arnauld.

\$\endgroup\$
4
\$\begingroup\$

Haskell, 79 bytes

(""%)
(a:b)!(c:d)|a==c=1+b!d
_!_=0
a%c@(e:d)=maximum[a!c,""%d,(a++[e])%d]
_%_=0

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ It looks like first argument of % can accumulate a non-contiguous subsequence, giving false positives like 2 for aa in axayaa, \$\endgroup\$ – xnor Feb 21 '18 at 7:47
  • \$\begingroup\$ What @xnor said. I think the recursive call to a%d is wrong, but also unnecessary. Which also means you can use max instead of maximum. \$\endgroup\$ – Ørjan Johansen Feb 21 '18 at 7:48
  • 1
    \$\begingroup\$ I think changing a%d to ""%d fixes it. \$\endgroup\$ – xnor Feb 21 '18 at 8:16
  • \$\begingroup\$ Oh right, it's still needed (and sound) when a is empty. \$\endgroup\$ – Ørjan Johansen Feb 21 '18 at 9:01
  • 1
    \$\begingroup\$ I think sum[1|(x,y)<-zip a c,x==y] can be used instead of a!c. \$\endgroup\$ – Laikoni Feb 21 '18 at 9:05
3
\$\begingroup\$

Python 3, 75 72 bytes

f=lambda s,n=0:s[n:]and max(n*(s[:n]in s[n:]),f(s,n+1))or n and f(s[1:])

Try it online!

\$\endgroup\$
2
\$\begingroup\$

JavaScript, 120

function r(a,b,m){return b=-~b,t=a.slice(0,b),n=a.indexOf(t,b),m=b>m&&!~n?m:b,a!=t&&r(a,b,m)||(a?r(a.slice(1),m,m):~-m)}
\$\endgroup\$
2
\$\begingroup\$

Husk, 11 bytes

L►L§fo↓2`xQ

Try it online!

Note: Husk is newer than this challenge.

Explanation

L►L§fo↓2`xQ  Implicit input, say x = "ababc"
          Q  Nonempty substrings: ["a","b","ab",..,"ababc"]
    f        Keep those that satisfy this:
              Take s = "ab" as an example.
   §    `x    Split x along s: ["","","c"]
     o↓2      Drop the first two pieces: ["c"]
              This is truthy (i.e. nonempty).
             Result is ["a","b","ab","a","b","ab"]
 ►L          Take element with maximal length: "ab"
             If the list is empty, "" is used instead.
L            Length: 2
\$\endgroup\$
2
\$\begingroup\$

Perl 5 with -p, 40 bytes

$_+=(sort map{y///c}/(?=(.+).*\1)/g)[-1]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 75 65 bytes

10 bytes saved due to @JingHwan Min.

Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]&

Anonymous function. Takes a string as input, and returns a number as output.

\$\endgroup\$
  • \$\begingroup\$ I don't think you need the beginning and ending BlankNullSequence (___) when Overlaps->All is there. Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]& would be just fine. \$\endgroup\$ – JungHwan Min Dec 18 '16 at 7:03
  • \$\begingroup\$ @JungHwanMin Thanks, was confusing it with StringReplace :P \$\endgroup\$ – LegionMammal978 Dec 18 '16 at 12:23
1
\$\begingroup\$

Pyth - 16 bytes

I need to golf the converting all the strings to lengths and finding the max.

eSlM+ksmft/dTd./

Test Suite.

\$\endgroup\$
1
\$\begingroup\$

Clojure, 112 bytes

#(apply max(for[R[(range(count %))]j R i R](let[[b e](split-at i(drop j %))](if((set(partition i 1 e))b)i 0)))))

loops twice over numbers 0 to n - 1 (n being length of the string), drops j characters and splits the remainder into "beginning" and "end" parts. Creates a set of all substrings at e of length b and uses it as a function to check if b is found from there. Returns the length of b if found and 0 otherwise, returns the max of these values.

Would be interesting to see a shorter version.

\$\endgroup\$
1
\$\begingroup\$

Retina, 24 bytes

L$v`(.*).*\1
$.1
N`
G-1`

Try it online!

A warmup for me to learn the new features of Retina 1.

Explanation

L$v`(.*).*\1
$.1

A List stage, this returns all the matches for the regex (.*).*\1, wich matches any pattern of the form "ABA", where A and B are two arbitrary substrings (possibly empty). The additional options given to this stage are v, which considers overlapping matches, and $ which applies a substitution to each of the matches before returning it: the substitution is indicated in the second line, and corresponds to the length (.) of the first capturing group (which would be the substring "A" in the previous example).

N`

We now have all the lengths of repeated substrings, this stage simply sorts them in numerical order, from the shortest to the longest.

G-1`

Finally, this grep stage (G) keeps only the last (-1) result, which is the length of the longest repeated substring.

\$\endgroup\$
0
\$\begingroup\$

Javascript, 165 bytes

function a(s){var l=s.length/2,z=1,f='';while(z<=l){var t=s.substr(0,z),c=0;for(var i=0;i<s.length;i++){if(s.substr(i,z)===t){c++;if(c>1){f=t}}}z++}return f.length}

Test Cases

console.log(a('abcabcabcabc')) // Output 6
console.log(a('xyz'))          // Output 0
console.log(a('aaaaaaa'));     // Output 3
console.log(a('abcdefabc'));   // Output 3
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf. Unfortunately, this returns 2 for input ababcabcabcabcab, but the string cabcab is repeated . \$\endgroup\$ – Dennis Dec 17 '16 at 5:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.