20
\$\begingroup\$

A string of characters repeats if it contains two consecutive substrings that are equivalent.

For example, 2034384538452 repeats as it contains 3845 twice, consecutively.

Therefore, your challenge is to decide whether a string contains a repeating substring. You may take the input as a string or an array of characters.

You will never receive an empty input, and the length of the substring (if it exists) may be 1 or more.

I use 1 and 0 here as my truthy and falsy values, but you may use different values, as long as they are truthy and falsy in your language.

Examples:

abcab -> 0
bdefdefg -> 1
Hello, World! -> 1
pp.pp/pp -> 1
q -> 0
21020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120210121020121012021012102012021020121012021012102012101202102012021012102012021020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120210121020120210201210120210201202101210201210120210121020120210201210120210121020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120 -> 0

(The last example was generated from the amount of ones between each zero in the Thue-Morse sequence)

\$\endgroup\$
15
  • 2
    \$\begingroup\$ Can I use inconsistent values, as long as they're still appropriately truthy or falsey? \$\endgroup\$ Jun 10 '17 at 10:18
  • \$\begingroup\$ @EriktheOutgolfer Of course \$\endgroup\$
    – Okx
    Jun 10 '17 at 10:22
  • \$\begingroup\$ @trichoplax I think he means consecutive subsequences of length >= 1. \$\endgroup\$ Jun 10 '17 at 10:31
  • \$\begingroup\$ @EriktheOutgolfer "consecutive" was the word I missed. Thank you - it makes perfect sense now. \$\endgroup\$
    – trichoplax
    Jun 10 '17 at 10:33
  • \$\begingroup\$ Can we output 1 for falsey and 0 for truthy instead? \$\endgroup\$
    – user41805
    Jun 10 '17 at 10:57

18 Answers 18

12
\$\begingroup\$

Retina, 6 bytes

(.+)\1

Try it online!

Positive value for truthy; zero for falsey.

How it works

Returns the number of matches of the regex /(.+)\1/g.

\$\endgroup\$
10
\$\begingroup\$

Brachylog, 3 bytes

s~j

Try it online!

s~j
s    exists a sublist of input
 ~j  which is the result of a juxtaposition of something
\$\endgroup\$
7
\$\begingroup\$

Jelly, 6 5 bytes

Ẇµ;"f

This is a full program. TIO can't handle the last test case without truncating it.

Try it online! (last test case truncated to 250 digits)

How it works

Ẇµ;"f  Main link. Argument: s (string)

Ẇ      Words; generate all substrings of s.
 µ     New chain. Argument: A (substring array)
  ;"   Vectorized concatenation; concatenate each substring with itself.
    f  Filter; keep "doubled" substrings that are also substrings.
       This keeps non-empty string iff the output should be truthy, producing
       non-empty output (truthy) in this case and empty output (falsy) otherwise.
\$\endgroup\$
0
5
\$\begingroup\$

Mathematica, 32 bytes

StringMatchQ[___~~x__~~x__~~___]
\$\endgroup\$
3
  • \$\begingroup\$ Doesn't this require that the repeating string subsegments be adjacent? \$\endgroup\$
    – DavidC
    Jun 10 '17 at 20:49
  • 1
    \$\begingroup\$ @Svetlana, you are correct! I hadn't taken abcab-> 0 into account. \$\endgroup\$
    – DavidC
    Jun 11 '17 at 11:32
  • 1
    \$\begingroup\$ StringContainsQ[x__~~x__] and !StringFreeQ[#,x__~~x__]& are both shorter. \$\endgroup\$
    – ngenisis
    Jun 21 '17 at 19:21
5
\$\begingroup\$

Java, 27 bytes

a->a.matches(".*(.+)\\1.*")

Pretty much a duplicate of the Retina answer, but there's no way Java's getting any shorter.

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

05AB1E, 5 bytes

Œ2×åZ

Try it online!

Outputs 1 as truthy value and 0 as falsy value

Explanation

Œ2×åZ
Π    # Substrings of input
 2×   # duplicate them (vectorized)
   å  # Is the element in the input? (vectorized)
    Z # Maximum value from list of elements
\$\endgroup\$
4
\$\begingroup\$

Python, 38 bytes

import re
re.compile(r'(.+)\1').search

Try it online!

Yawn, a regex. Checks if the string contains a string of one of more characters .+ followed by that same string that was just captured. The output search object is Truthy if there's at least one match, as can be checked by bool.

Using compile here saves over writing a lambda:

lambda s:re.search(r'(.+)\1',s)

Python, 54 bytes

f=lambda s:s>''and(s in(s*2)[1:-1])|f(s[1:])|f(s[:-1])

Try it online!

Searches for a substring that is composed two or more equal strings concatenated, as checked by s in(s*2)[1:-1] as in this answer. Substrings are generated recursively by choosing to cut either the first or last character. This is exponential, so it times out on the large test case.

Near misses:

f=lambda s,p='':s and(s==p)*s+f(s[1:],p+s[0])+f(s[:-1])
f=lambda s,i=1:s[i:]and(2*s[:i]in s)*s+f(s[1:])+f(s,i+1)

The first one doesn't use Python's in for checking substrings, and so could be adapted to other languages.

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

Pyth - 10 9 8 bytes

f}+TTQ.:

Returns a list of all the repeating substrings (which if there aren't any, is an empty list, which is falsy)

Try It

Explanation:

f}+TTQ.:
      .:    # All substrings of the input (implicit):
f           # filter the list of substrings T by whether...
  +TT       # ...the concatenation of the substring with itself...
 }   Q      # ...is a substring of the input
\$\endgroup\$
1
  • 1
    \$\begingroup\$ If you assume that the input is in quotes f}+TTQ.: works from 1 Byte less: link \$\endgroup\$
    – KarlKastor
    Jun 12 '17 at 7:16
3
\$\begingroup\$

Cheddar, 60 bytes

n->(|>n.len).any(i->(|>i).any(j->n.index(n.slice(j,i)*2)+1))

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ You can golf: @.test(/(.+)\1/) \$\endgroup\$
    – Downgoat
    Jun 21 '17 at 17:34
  • \$\begingroup\$ @Downgoat You should just submit that as another answer, really. \$\endgroup\$
    – Leaky Nun
    Jun 21 '17 at 17:39
3
\$\begingroup\$

PHP, 32 bytes

<?=preg_match('#(.+)\1#',$argn);

Try it online!

PHP, 38 bytes

<?=preg_match('#(.+)(?(1)\1)#',$argn);

Try it online!

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

Python 3, 73 66 bytes

-7 bytes thanks to @LeakyNun

lambda s:any(2*s[j:i]in s for i in range(len(s))for j in range(i))

Try it online!

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

Perl 6, 11 bytes

{?/(.+)$0/}

Test it

Expanded:

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

  ?      # Boolify the following
         # (need something here so it runs the regex instead of returning it)

  /      # a regex that implicitly matches against 「$_」
    (.+) # one or more characters stored in $0
     $0  # that string of characters again
  /
}
\$\endgroup\$
2
\$\begingroup\$

PHP, 32 bytes

<?=preg_match('#(.+)\1#',$argn);

Run as pipe with -F. Sorry Jörg, I hadn´t noticed You had posted the same.

non-regex version, 84 82 bytes

    for($s=$argn;++$e;)for($i=0;~$s[$i];)substr($s,$i,$e)==substr($s,$e+$i++,$e)&&die

exits with return code 0 for a repeat, times out (and exits with error) for none. Run as pipe with -nr.
assumes printable ASCII input; replace ~ with a& for any ASCII.

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

JavaScript (ES6), 19 bytes

s=>/(.+)\1/.test(s)
\$\endgroup\$
10
  • \$\begingroup\$ How about /(.+)\1/.test? \$\endgroup\$
    – Luke
    Jun 10 '17 at 11:13
  • \$\begingroup\$ That's what I have, @Luke. \$\endgroup\$
    – Shaggy
    Jun 10 '17 at 11:17
  • \$\begingroup\$ @Shaggy I believe he means /(.+)\1/.test itself as the complete submission. \$\endgroup\$
    – Leaky Nun
    Jun 10 '17 at 12:59
  • \$\begingroup\$ @Luke /(.+)\1/.test is unbound (has no this). f=/(.+)\1/.test;f('aa') wouldn't work, for example. You would need /./.test.bind(/(.+)\1/) \$\endgroup\$
    – Artyer
    Jun 10 '17 at 20:33
  • \$\begingroup\$ You can golf to: ::/(.+)\1/.test (15 bytes) \$\endgroup\$
    – Downgoat
    Jun 21 '17 at 17:33
1
\$\begingroup\$

Pyth, 15 bytes

.E.nm.bqNYtdd./

Try it!

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

V, 6 bytes

ø¨.«©±

Try it online!

Test Suite!

The program outputs 0 for falsey values, and a positive integer for positive values.

(Note that there was a small bug, so I had to gain 1 byte. Now after the bugfix, I will be able to replace with \x82)

Explanation

ø                     " This is a recent addition to V. This command takes in a regex
                      " and replaces the line with the number of matches of the regex
 ¨.«©±                " The compressed regex. This decompresses to \(.\+\)\1
\$\endgroup\$
1
\$\begingroup\$

Japt, 8 + 1 = 9 8 bytes

f"(.+)%1

Try it online. Outputs null for falsy, and an array containing all the repeating strings for truthy.

Explanation

 f"(.+)%1
Uf"(.+)%1" # Implicit input and string termination
Uf         # Find in the input
  "(.+)%1" #   a sequence followed by itself
 f         # and return the matched substring
           # output the return value
\$\endgroup\$
5
  • \$\begingroup\$ Inconsistent output values are permitted so you could use è to return the number of matches and drop the flag. \$\endgroup\$
    – Shaggy
    Jun 10 '17 at 11:11
  • \$\begingroup\$ Yeah. I could also just drop the flag to return the match itself, since no match returns null, which is falsy. \$\endgroup\$
    – Luke
    Jun 10 '17 at 11:13
  • \$\begingroup\$ For input 00, it outputs 00. Are you sure this is truthy in Japt? \$\endgroup\$
    – Okx
    Jun 10 '17 at 11:25
  • \$\begingroup\$ @Okx The string "00" is. \$\endgroup\$ Jun 10 '17 at 17:21
  • \$\begingroup\$ @Okx; try this. The -Q flag "prettyprints" the output so you can see that it's an array containing a single string. \$\endgroup\$
    – Shaggy
    Jun 12 '17 at 14:53
0
\$\begingroup\$

Cheddar, 16 bytes

@.test(/(.+)\1/)

This is a function. Try it online!

\$\endgroup\$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .