# Repeat after me!

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.

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

## 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.)

# 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.

• All hail Jelly, the ultimate code golf language! Dec 17 '16 at 17:01
• œ-Q is really neat.
– Lynn
Dec 18 '16 at 17:16

# 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

}


# Retina, 3532 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

• You can save two bytes by using M%. as the second stage. Dec 17 '16 at 8:31

## JavaScript (ES6), 7968 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.

(""%)
(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!

• It looks like first argument of % can accumulate a non-contiguous subsequence, giving false positives like 2 for aa in axayaa,
– xnor
Feb 21 '18 at 7:47
• 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. Feb 21 '18 at 7:48
• I think changing a%d to ""%d fixes it.
– xnor
Feb 21 '18 at 8:16
• Oh right, it's still needed (and sound) when a is empty. Feb 21 '18 at 9:01
• I think sum[1|(x,y)<-zip a c,x==y] can be used instead of a!c. Feb 21 '18 at 9:05

# 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!

# Husk, 11 bytes

L►L§fo↓2xQ


Try it online!

Note: Husk is newer than this challenge.

## Explanation

L►L§fo↓2xQ  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


# 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)}


$_+=(sort map{y///c}/(?=(.+).*\1)/g)[-1]  Try it online! # 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. • 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. Dec 18 '16 at 7:03 • @JungHwanMin Thanks, was confusing it with StringReplace :P Dec 18 '16 at 12:23 # Pyth - 16 bytes I need to golf the converting all the strings to lengths and finding the max. eSlM+ksmft/dTd./  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. # 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.

## 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

• Welcome to Programming Puzzles & Code Golf. Unfortunately, this returns 2 for input ababcabcabcabcab, but the string cabcab is repeated . Dec 17 '16 at 5:20