Divisor of a string

Question

Challenge

Given a positive-length string \$S\$, a divisor of \$S\$ is another (not necessarily distinct) string for which there exists a number \$a\$ such that when we repeat the divisor \$a\$ times, we get the string \$S\$.

For example, the string abcd is a divisor of the string abcdabcd with \$a=2\$.

Your challenge is, given a positive-length string \$S\$, output all of \$S\$'s divisors.

For example, the string aaaa has three divisors: a, aa, and aaaa.

Input/Output

Input/output can be taken in any reasonable format for taking a string and returning the set of divisors of that string.

The input string will only has lowercase characters, and it contains no whitespace or special characters.

The output list should not contains any duplicates. The strings can appear in any order.

Testcase:

Input -> Output
abcdabcd -> abcd, abcdabcd
aaa -> a, aaa
aaaaaaaa -> a, aa, aaaa, aaaaaaaa
abcdef -> abcdef 

This is code-golf, so shortest answer (in bytes) wins!

Answer 1

Brachylog, 3 bytes

ġ=h

Try it online!

Generator.

ġ      Split the input into (roughly) equal slices.
  h    Output one of them
 =     if they're all equal.

Answer 2

Python, 53 bytes

lambda s,t="":[t for c in s if~-any(s.split(t:=t+c))]

Attempt This Online!

Answer 3

Regex (ECMAScript 2018 or better), 17 bytes

(?<=(.*))(?=\1*$)

Try it online! - ECMAScript 2018
Try it online! - Python (import regex)
Try it online! - .NET
Try it on regex101! - ECMAScript 2018 or .NET

Returns its output as the list of matches' \1 captures.

Ports:
Try it online! - Java, 18 bytes: (?<=(^.*))(?=\1*$)
Try it online! - Perl, 31 bytes: (?=(.*)).((?<=(?=^\1*$|(?2)).))
Try it online! - PCRE2, 31 bytes - same as above
Try it on regex101! - PCRE2
Try it online! - PCRE, 33 bytes: (?=(.*)).((?<=(?=‍¶|^\1*$|(?2)).))
Try it on regex101! - PCRE1

Answer 4

05AB1E, 6 5 bytes

ηʒKõQ

Try it online or verify all test cases.

Explanation:

η      # Get all prefixes of the (implicit) input-string
 ʒ     # Filter it by:
  K    #  Remove all occurrences of the prefix-string from the (implicit) input
   õQ  #  Check if what remains is an empty string
       # (after which the filtered list is output implicitly as result)

Answer 5

Factor + grouping.extras, ^{73 70 57} 48 bytes

[ dup head-clump [ ""replace ""= ] with filter ]

Attempt This Online!

-13 bytes and then -9 more by porting @KevinCruijssen's 05AB1E answer (and then improved version)!

Answer 6

Curry (PAKCS), 26 bytes

f(g a)=a
g a|a>""=a++g a?a

Try it online!

Answer 7

Haskell, 42 bytes

f s|p<-scanr(:)""s=[t|t<-p,a<-p,(a*>t)==s]

Try it online!

scanr(:)""s lists the suffixes of the input s. For each suffix t, we look for a suffix a where repeating t once for each character of a (a*>t) gives the original string s.

Answer 8

J, 19 bytes

<\#~<=<\$~&.>#+#\|#

Try it online!

• <\$~ Cyclically extend each prefix to the following length:
  • #+#\|# Length of input # + the remainder when we divide that prefix's length into the input's length #\|#. This ensures non-divisible prefixes won't match.
• <= Which of the extended prefixes matches the input?
• <\#~ Filter all prefixes using that mask.

Answer 9

K (ngn/k), 26 bytes

{((#(,x)^,\(#x)#,:)')_,\x}

Try it online!

I guess this is somewhat a new strategy. For each prefix, tests if the original input appears in the list of 1..(length of input) repetitions of the prefix.

{((#(,x)^,\(#x)#,:)')_,\x}  x: input string of length n
                      ,\x   prefixes
 ((               )')_      remove the items that give nonzero:
         ,\(#x)#,:            repeat the prefix 1..n times
    (,x)^                     set minus from the singleton list of x
   #                          is x still there?

Answer 10

Jelly, 8 6 bytes

sJEƇḢ€

Try it online!

Port of my Brachylog solution.

s         Slice the input into chunks of
 J        every length.
  EƇ      Keep only partitions with all equal elements,
    Ḣ€    and return the first element of each remaining partition.

Answer 11

K (ngn/k), 19 bytes

{(x{#,/y\x}/:)_,\x}

Try it online!

,\x get all prefixes of the input
... _ discard a prefix if:
  y\x split the input by this prefix
  ,/ concatenate parts into a single string
  # length of this string is non-zero.

Answer 12

Ruby, 53 52 bytes

->s{(1..k=s.size).map{|x|w=s[0,x];w*k==s*x ?w:s}|[]}

Try it online!

Answer 13

Vyxal, 8 6 bytes

øṖ~≈vh

Try it Online!

Port of Unrelated String's Jelly answer.

Porting Kevin Cruijssen's 05AB1E answer would be 6 bytes as well:

Vyxal, 6 bytes

¦'?$o¬

Try it Online!

Answer 14

C# (Visual C# Interactive Compiler), 68, 58 bytes

Iterate and replace every substring starting from index 0 and check if it equals an empty string

Credit to @Acer for the syntatic sugar

s=>s.Select((_,i)=>s[..++i]).Where(x=>s.Replace(x,"")=="")

Try it online!

Answer 15

Nibbles, 5.5 bytes (11 nibbles)

|.,,$<$@~%@

|.,,$<$@~%@
   ,            # get the length of
    $           # the input string
  ,             # and make a range 1..length,
 .              # now, map over these values
     <$         # taking that number of characters
       @        # from the input string
                # (this gets the prefixes),
|               # now, filter these to keep only those that
        ~       # are falsy 
         %@     # when we use them to split the input string
                # (so, string-divisors yield the empty string)

Answer 16

Python, 65 63 bytes

lambda s:[s[:i]for i in range(1,len(s)+1)if len(s)//i*s[:i]==s]

Attempt This Online!

A very unclever solution.

---

Saved -2 bytes from @ruancornelli.

Answer 17

Haskell, 65 bytes

d s|r<-[1..length s]=[z|z<-(`take`s)<$>r,s`elem`[[1..n]>>z|n<-r]]

Try it online!

Answer 18

Knight, 32 bytes

;=x=yP Wx;I?y*x/LyLxOxN=xGxF-LxT

Try it online!

; = x (= y (PROMPT))                            # x = y = input()
: WHILE x                                       # while x != "":
    ; IF (? y (* x (/ (LENGTH y) (LENGTH x))))  #   if y == x * (len(y) / len(x)):
        : OUTPUT x                              #     print(x)
        : NULL                                  #   else: (do nothing)
    : = x (GET x 0 (- (LENGTH x) 1))            #   x = x[:-1]

Answer 19

Python 3.8, 56 bytes

-7 bytes thanks to user loopy walt

lambda s,d='':[d for c in s if len(s)//len(d:=d+c)*d==s]

Attempt This Online!

Answer 20

Ruby, 43 bytes

->s{(s+?␀+s).scan(/(?=(.+)␀\1*$)/).flatten}

Try it online!

This concatenates the string to itself with a NUL (ASCII 0) character between, in order to use a regex to find all matches' \1 captures. Since Ruby does not have variable-length lookbehind and can't emulate it with recursion, this approach couldn't work on the unmodified string.

Since this does a manipulation on the input before working on it, thus departing from my idea of what a pure regex is, I'm posting this as a separate answer.

Ruby, _³⁵ 34 bytes

->s{(s+?␀+s).scan /(?=(.+)␀\1*$)/}

Try it online!

If it is acceptable to return the output as a list of one-element string lists, then this answer can be even shorter. This returns, for example, [["abcdabcd"], ["abcd"]] instead of ["abcdabcd", "abcd"].

Ruby, _⁵⁰ 47 bytes

->s{(s+s).scan /(?=(.+)(?=.{#{s.size}}$)\1*$)/}

Try it online!

This approach works even on strings containing NUL(s), as it uses the length of the string (rather than a delimiter) as a marker. As with the 35 byte solution above, it returns a list of one-element string lists.

Answer 21

Raku, 25 bytes

{~«m:ex/^(.+)$0*$/»[0]}

Try it online!

m/^(.+)$0*$/ looks for patterns of letters which, repeated, comprise the entire string. The :exhaustive flag on the match operation (shortenable to :ex) looks for every possible match, not just one. Then »[0] extracts just the first submatch (ie, the divisor) from every match, and ~« stringifies each of those match objects.

Answer 22

Retina 0.8.2, 17 bytes

&!`(.+)$(?<=^\1+)

Try it online! Link includes test cases. Explanation:

&!`

List all overlapping matches.

(.+)$

Match any suffix...

(?<=^\1+)

... which can be repeated to recreate the original string.

Answer 23

Husk, 7 bytes

fȯEC¹Lḣ

Try it online!

      ḣ     # get the heads (prefixes) of the input
f           # filter these to keep only truthy by
 ȯ          # result of 3 functions:
   C¹       #  cut the input into pieces
     L      #  with the length of each prefix
  E         #  and check if they're all equal

Alternative, also 7 bytes

foE`x¹ḣ

Try it online!

foE`x¹ḣ
      ḣ     # get the heads (prefixes) of the input
f           # filter these to keep only truthy by
 o          # result of 2 functions:
   x        #  split on given substring
  `         #  (with reversed arguments)
    ¹       #  the input 
            #  (note that first element will always be empty list
            #  when splitting using a prefix)
  E         #  and check if they're all equal
            #  (which will only be the case if all are emty lists, 
            3  meaning that the input was a multiple of the substring)

Answer 24

Charcoal, 15 bytes

ΦＥθ…θ⊕κ№Ｅθ×ι⊕μθ

Try it online! Link is to verbose version of code. Explanation:

  θ             Input string
 Ｅ              Map over characters
    θ           Input string
   …            Truncated to length
      κ         Current index
     ⊕          Incremented
Φ               Filtered where
         θ      Input string
        Ｅ       Map over characters
           ι    Current prefix
          ×     Repeated by
             μ  Inner index
            ⊕   Incremented
       №        Contains
              θ Input string
                Implicitly print

Answer 25

sed -n, 58 46 bytes

s/^/\n/
:a
/^\(.*\)\n\1*$/P
s/\n\(.\)/\1\n/
ta

Attempt This Online!

Answer 26

Rust, 108 106 bytes

-2 bytes thanks to alephalpha

|a:&str|(1..=a.len()).map(|k|a[..k].repeat(1)).filter(|z|z.repeat(a.len()/z.len())==a).collect::<Vec<_>>()

Playground Link

Answer 27

Haskell + hgl, 12 bytes

he<<fl lq<pt

Attempt This Online!

Explanation

• pt gets all ways to partition the input into non-empty lists
• fl lq filters out all items with duplicates
• he takes the first value in each result

Reflection

• A function that gives partitions satisfying a predicate would be immensely useful here. This could be he<<pST lq
• Similarly we should add a function that gives all partitions where the elements satisfy a predicate.
• A function that gives all permutations with equal size would not save any bytes here, but it would make this answer a lot faster to run and would probably be useful in the future.
• ƥ, mP, ms and mS all need flipped versions.
• A prefix and suffix filter would be useful. There are currently functions to get the longest suffix/prefix satisfying a predicate but not all.
• Shortcuts to check if a list has a particular length would be useful. There are already ones for checking if it is less than or greater than a value.

Answer 28

Arturo, 56 bytes

$[s][select map 1..size s=>[take s]'y->""=replace s y""]

Try it

Answer 29

Zsh, 47 bytes

for c (${(s..)1})s+=$c&&[[ $1 = ($s)# ]]&&<<<$s

Try it online!

Fairly straightforward:

for c (${(s..)1})       # (s)split $1 on '' (into characters)
    s+=$c &&            # append character to $s
    [[ $1 = ($s)# ]] && # if $1 equals $s repeated
    <<< $s              # output $s

Answer 30

Perl -p, 22 bytes

/^(.*)\1+$(??{say$1})/

Try it online!

This uses a "postponed" regular subexpression embedded code block to accomplish the same thing as Raku's exhaustive verb (which is used in Sean's answer), enumerating all possible matches, not just the ones (the one, in fact) that would be found normally.

Once a match of ^(.*)\1+$ that would be successful finishes, the embedded code block is triggered, and say$1 prints the value of the \1 capture group. Since it's of the "postponed" type, it then dynamically compiles the result of say$1 (which is the boolean 1) into the regex, causing the match to fail, since 1 can never occur after the end of a string. A literal 1 placed after the $ would cause the match to fail and give up, due to Perl's regex optimization. But since it's dynamically compiled into the regex, the result of executing a piece of code, Perl doesn't know that it will be 1 every time, so it actually allows the regex to backtrack and try other possible matches.

The regex is intentionally set to not let \1 match the entire input string, only strict substrings. ^(.*)\1*$ would be the version that would also match the entire string. But that is left out, because once the program finishes, Perl's -p flag causes $_ to be printed. That way, all of the string's divisors, including itself, are outputted.

Embedded code capability is a rare thing in regex engines. As far as I know, the only ones that have it are Perl and Raku (embedded code blocks) and PCRE (callouts). It appears that MATLAB allows execution of MATLAB code inside a regex, but I have not tested that yet (and am not sure if GNU Octave, which uses PCRE, has that functionality, or if MATLAB even also uses PCRE).

Another thing to note is that inputs followed by a newline (rather than EOF) will have that newline included in the contents of $_, and this program doesn't use chomp. But that doesn't matter, since $ matches both the true end of string, and the position immediately before a newline at the end of the string, if there is one. This is the case regardless of whether the multiline flag is enabled (which it is not, by default). This is a case where that behavior (as opposed to \z, which strictly matches the end of string) is helpful.

Perl -n, 22 bytes

/^(.*)\1*$(??{say$1})/

Try it online!

This is really the more logical version, printing the divisors in a consistent order. But I'm keeping the -p version up here, since -p is much more commonly used in answers, and as the way flags are treated (as distinct languages, in a certain abstract way) it lets it be in the same playing field as those -p answers. Not to mention that the workaround it uses is kind of fun.