Exploded substrings

Question

Introduction

Let's observe the string abc. The substrings that can be made from this are:

a, ab, abc, b, bc, c

We now need to align them under the initial string, like this:

abc
a
 b
  c
ab
 bc
abc

The order of the string doesn't matter, so this is also perfectly valid:

abc
a
ab
abc
 b
 bc
  c

So, the substring is positioned under the location of the substring in the initial string. So for abcdef and the substring cde, it would look like this:

abcdef
  cde

The Task

The task is to align all substrings with a length greater than 0, like shown above. You can assume that the string itself will only contain alphabetic characters and has at least 1 character. For the padding, you can use a space or some other non-alphabetic printable ASCII character (32 - 127). Maybe not necessary to mention, but the string itself will only contain unique characters, so not like aba, since the a occurs twice.

Test cases

Input: abcde

Possible output:

a
ab
abc
abcd
abcde
 b
 bc
 bcd
 bcde
  c
  cd
  cde
   d
   de
    e

Input: abcdefghij

Possible output:

a
ab
abc
abcd
abcde
abcdef
abcdefg
abcdefgh
abcdefghi
abcdefghij
 b
 bc
 bcd
 bcde
 bcdef
 bcdefg
 bcdefgh
 bcdefghi
 bcdefghij
  c
  cd
  cde
  cdef
  cdefg
  cdefgh
  cdefghi
  cdefghij
   d
   de
   def
   defg
   defgh
   defghi
   defghij
    e
    ef
    efg
    efgh
    efghi
    efghij
     f
     fg
     fgh
     fghi
     fghij
      g
      gh
      ghi
      ghij
       h
       hi
       hij
        i
        ij
         j

This is code-golf, so the submission with the least amount of bytes wins!

Answer 1

Perl, 32 28 24 bytes

Includes +1 for -n

Code:

/.+(??{say$"x"@-".$&})/

Run with the string on STDIN:

perl -nE '/.+(??{say$"x"@-".$&})/' <<< abcd

The golfing languages are so close and yet so far away...

Explanation

/.+/ matches a substring. Unfortunately it stops once it matched one. So I use the runtime regex construct (??{}) to extend the regex so it fails and backtracking will try the following substring, in the end trying them all before giving up in disgust.

Inside the (??{}) I print the current substring prefixed by as many spaces as the offset of the substring using $"x"@-"

So the output neatly documents how regex backtracking works:

abcd
abc
ab
a
 bcd
 bc
 b
  cd
  c
   d

Answer 2

MATL, 20 18 bytes

Inspired by the pattern of substrings generated by @aditsu's answer

tt!+gR*c`t3Lt3$)tn

Try it online!

The pattern of substrings is generated by an upper triangular matrix the same size as the input, and all submatrices obtained by successively removing the last row and column.

Explanation

t         % implicit input. Duplicate
t!+g      % square matrix with size as input
R         % keep upper triangular part
*c        % multiply element-wise with broadcast. Convert to char
`         % do...while
  t       %   duplicate
  3Lt3$)  %   remove last row and column
  tn      %   number of remaining elements. Used as loop condition
          % implicitly end loop and display

---

Old approach (Cartesian power)

I'm keeping this approach in case it serves as inspiration for other answers

tn0:2Z^!S!2\Xu4LY)*c

In the online compiler this runs out of memory for the longest test case.

Try it online!

Explanation

This generates all patterns of values 0, 1 and 2 in increasing order, and then transforms 2 into 0. This gives all possible patterns of 0 and 1 where the 1 values are contiguous. These are used to mark which characters are taken from the original string.

As an example, for string 'abc' the patterns are generated as follows. First the Cartesian power of [0 1 2] raised to the number of input characters is obtained:

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
···
2 2 1
2 2 2

Sorting each row gives

0 0 0
0 0 1
0 0 2
0 0 1
0 1 1
···
1 2 2
2 2 2

Transforming 2 into 0 (i.e. mod(...,2)) and removing duplicate rows gives the final pattern

0 0 0
0 0 1
0 1 1
0 1 0
1 1 1
1 1 0
1 0 0

in which each row is a mask corresponding to a (contiguous) substring. The first row needs to be removed because it corresponds to the empty substring.

t      % Implicitly get input. Duplicate
n      % Number of elements
0:2    % Vector [0 1 2]
Z^     % Cartesian power. Each result is a row
!S!    % Sort each row
2\     % Modulo 2: transform 2 into 0
Xu     % Unique rows
4LY)   % Remove first (corresponds to the empty substring)
*      % Element-wise multiplication by original string
c      % Convert to char. Implicitly display

Answer 3

Retina, 48 32 31 bytes

Thanks to Kenny Lau for saving 3 bytes and paving the way for many more.

Byte count assumes ISO 8859-1 encoding.

M&!r`.+
%+`( *)\S(.+)$
$&¶$1 $2

Try it online!

Order of the generated substrings:

abcde
 bcde
  cde
   de
    e
abcd
 bcd
  cd
   d
abc
 bc
  c
ab
 b
a

Explanation

M&!r`.+

This gets us all the prefixes of the input. This is done by matching (M) any substring (.+) starting from the end (r), considering overlapping matches (&) and returning all of those matches joined with linefeeds (!).

Now all we need to do is carve out the successive prefixes of those prefixes (by replacing them with spaces). We do this step by step with a loop:

%+`( *)\S(.+)$
$&¶$1 $2

The % means that this entire thing is done to each line individually (considering it a separate string for time being, and joining it all back together with linefeeds at the end). The + tells Retina to run this substitution in a loop until the output stops changing (which in this case means that the regex no longer matches). The regex then tries to match the last line of the input with at least two non-space characters, and appends a new row where the first of those is replaced with a space.

Answer 4

Pyth, 14 13 10 bytes

Thanks to @FryAmTheEggman for saving 3 bytes.

jmXQ-Qd;.:

Try it online!

Answer 5

Oracle SQL 11.2, 146 bytes

WITH v AS(SELECT LEVEL i FROM DUAL CONNECT BY LEVEL<=LENGTH(:1))SELECT LPAD(SUBSTR(:1,s.i,l.i),s.i+l.i-1)FROM v s,v l WHERE s.i+l.i<=LENGTH(:1)+1;

Un-golfed

WITH v AS(SELECT LEVEL i FROM DUAL CONNECT BY LEVEL<=LENGTH(:1))
SELECT LPAD(SUBSTR(:1,s.i,l.i),s.i+l.i-1)
FROM   v s, v l
WHERE  s.i+l.i<=LENGTH(:1)+1

Answer 6

CJam, 20

q{__,{\_N+oSt}/;W<}h

Try it online

Explanation:

q           read the input (initial string)
{…}h        do … while
  _         copy the current string
  _,        copy and get the length
  {…}/      for each value (say i) from 0 to length-1
    \       bring the string to the top
    _N+o    make a copy, append a newline and print
    St      set the i'th element to S=" "
  ;         pop the last result (array full of spaces)
  W<        remove the last character of the current string
             if the string is empty, the do-while loop terminates

Answer 7

Python, 57 bytes

f=lambda s,p='':set(s)and{p+s}|f(s[1:],' '+p)|f(s[:-1],p)

Outputs a set like {' b', 'a', 'ab'}. The idea is to recurse down two branched that cut off the first or last character. The gives redundant outputs, but the set automatically removes duplicates. For alignment, every time the first character is cut off, a space is added to the prefix p, which is concatenated onto the front.

Answer 8

PowerShell v2+, 69 bytes

param($a)0..($b=$a.length-1)|%{($i=$_)..$b|%{" "*$i+-join$a[$i..$_]}}

Takes input $a, loops over the length (setting $b in the process for use later). Each outer loop, we loop up to $b again, setting $i for use later. Each inner loop, we output $i number of spaces concatenated with a slice of the input string. Since we're just looping through the string, this will actually handle any arbitrary string (duplicate letters, spaces, whatever).

Example

PS C:\Tools\Scripts\golfing> .\exploded-substrings.ps1 "Golfing"
G
Go
Gol
Golf
Golfi
Golfin
Golfing
 o
 ol
 olf
 olfi
 olfin
 olfing
  l
  lf
  lfi
  lfin
  lfing
   f
   fi
   fin
   fing
    i
    in
    ing
     n
     ng
      g

Answer 9

C#, 136 132 131 bytes

---

Golfed

String m(String s){String o="",e=o;for(int i=0,a,l=s.Length;i<l;i++,e+=" ")for(a=1;a+i<=l;a++)o+=e+s.Substring(i,a)+"\n";return o;}

---

Ungolfed

String m( String s ) {
    String o = "", e = o;

    for (int i = 0, a, l = s.Length; i < l; i++, e += " ")
        for (a = 1; a + i <= l; a++)
            o += e + s.Substring( i, a ) + "\n";

    return o;
}

---

Full code

    using System;
using System.Collections.Generic;

namespace Namespace {
    class Program {
        static void Main( string[] args ) {
            List<String> ls = new List<String>() {
                    "abcde",
                    "abcdefghijklmnop",
                    "0123456789",
                };

            foreach (String s in ls) {
                Console.WriteLine( s );
                Console.WriteLine( m( s ) );
                Console.WriteLine( "" );
            }

            Console.ReadLine();
        }

        static String m( String s ) {
            String o = "", e = o;

            for (int i = 0, a, l = s.Length; i < l; i++, e += " ")
                for (a = 1; a + i <= l; a++)
                    o += e + s.Substring( i, a ) + "\n";

            return o;
        }
    }
}

---

Releases

• v1.2 - -1 byte - Changed the String o="",e=""; to String o="",e=o; to save 1 byte. The idea was from Gallant ( I forgot to apply this part in the last update, I apologize. ).
• v1.1 - -4 bytes - Droped the brackets from the for loops and moved the e var space increment to the iterator zone of the outer for loop. The idea was from Gallant.
• v1.0 - 136 bytes - Initial solution.

Answer 10

Python 2.7, 70 82 bytes

I couldn't figure out how to get it on 1 line. Call with e("abcde",0)

def e(s,p):
 f=len(s)
 for x in range(f):print(' '*p+s[:x+1])
 if f>1:e(s[1:],p+1)

Answer 11

Python 3, 80 78 bytes

Loop through the number of spaces to prefix with and then the number of characters to end with.

lambda x:[print(' '*i+x[i:j+1])for i in range(len(x))for j in range(i,len(x))]

Edit: Removed spaces before the for loops.

Answer 12

MATL, 15 14 bytes

Saved one byte due to @LuisMendo's tip here!

tfWt2/!-RXzB*c

So many ways... had to find a new one. Happy bits! :)

Try it online!

Exploded

t       % duplicate input
f       % get indices of nonzero elements in vector (i.e. 1:n)
W       % 2 raised to array, element-wise: 2^(1:n)
t       % duplicate array
2/      % divide by 2: 2^(0:n-1)
!       % transpose array 
-       % element-wise subtraction (w/singleton expansion)
R       % upper triangular part
Xz      % nonzero elements
B       % convert from decimal to binary. Produces a logical array
*       % array product (element-wise, singleton expansion)
c       % convert to character array; 0's automatically converted to spaces

Answer 13

JavaScript (ES6), 89 bytes

document.write("<pre>"+(

s=>(a=[...s]).map((_,i)=>a.map((_,j)=>++j>i?r+=" ".repeat(i)+s.slice(i,j)+`
`:0),r="")&&r

)("abcde"))

Straight-forward approach. Output has a trailing newline.

Answer 14

JavaScript (ES6), 72

s=>{for(i=j=0;s[j]||s[j=++i];)console.log(' '.repeat(i)+s.slice(i,++j))}      

Answer 15

Pyth, 12 11 bytes

jm+*;xQdd.:

Sadly the question allows us to assume unique characters, so I just lookup the first position of the substring, and pad with spaces.

Answer 16

Mathematica 89 bytes

r@i_:=StringReplace[i,#->" "]&/@(Complement[y,#]&/@Subsequences[y=Characters@i])//Column

 

---

Explanation

i refers to the input string

Subsequences[y=Characters@i] returns all subsequences (represented lists of characters) of the input. (Subsequences was introduced in v. 10.4)

For each subsequence, Complement... returns those characters from the input string that are not present. Each of those characters is replaced by an empty space via StringReplace[i,#->" "].

Column displays the results in a single column. Each output string has the same number of characters, resulting in aligned letters.

---

r@"abcdefgh"

Answer 17

J, 32 29 28 bytes

(-@{.@i.|.])"1 a:>@-.~&,<\\.

This evaluates to a monadic verb. Try it here. Usage:

   f =: (-@{.@i.|.])"1 a:>@-.~&,<\\.
   f 'abe'
a  
ab 
abe
 b 
 be
  e

Explanation

As some other answers, I compute the index of occurrence of the first character of each substring. The substrings are stored in a matrix with trailing spaces, so I rotate them to the right by their index to get the right amount of padding. That one piece of whitespace between "1 and a: is really annoying...

(-@{.@i.|.])"1 a:>@-.~&,<\\.  Input is y
                        <\\.  Compute suffixes of prefixes of y, and put them in boxes.
                              This gives a 2D array of substrings in boxes.
                      &,      Flatten the array of boxes,
               a:  -.~        remove all empty strings, and
                 >@           open each box. This places the strings in a 2D matrix of
                              characters, with trailing spaces to make it rectangular.
(          )"1                Do this for each line x in the matrix:
      i.                        The index of every character of x in y.
 -@{.@                          Take the first one and negate it.
        |.]                     Rotate x to the left by that amount.
                                Since we negated the index, this rotates to the right.

Answer 18

JavaScript (Firefox 30-57), 65 63 bytes

s=>[for(c of(i=0,s))for(d of(t=r=i?t+' ':'',s.slice(i++)))r+=d]

Returns an array of strings. As ES6 it's 78 bytes:

s=>[...s].map((_,i,a)=>a.slice(i).map(c=>r.push(u+=c),t=u=i?t+' ':''),r=[])&&r

Answer 19

QBasic, 75 bytes

INPUT s$
FOR i=1TO LEN(s$)
FOR j=1TO i
LOCATE,j
?MID$(s$,j,i+1-j)
NEXT
NEXT

The basic double-FOR-loop strategy, modified a bit for QBasic's 1-based indexing. The main trick is LOCATE,j, which moves the cursor over to column j of the current line before printing. Since column 1 is the first column, this is equivalent to printing j-1 leading spaces.

Answer 20

Perl 6, 34 bytes

perl6 -ne 'm/^(.*)(.+)<{+put " "x$0.to,$1}>/'

m/       # match the input line
  ^      # from the start
  ( .* ) # 0 or more characters ( $0 )
  ( .+ ) # 1 or more characters ( $1 )

  <{ # match against the result of:

    +put # print with a trailing newline:
      " " x $0.to, # add the leading spaces
      $1           # the substring
  }>
/

The reason for the + before put is so that it returns 1 instead of True, which is guaranteed not to be in the input so it always has to backtrack.

$ perl6 -ne 'm/^(.*)(.+)<{+put " "x$0.to,$1}>/' <<< abcd

   d
  cd
  c
 bcd
 bc
 b
abcd
abc
ab
a

( If you want it in the opposite order use (.*?)(.+?) instead of (.*)(.+) )

This was inspired by the Perl 5 answer.

Answer 21

J, 35 23 22 bytes

[:;#\.<@{."_1|.\."1^:2

It took me a while but I finally optimized it.

Usage

   f =: [:;#\.<@{."_1|.\."1^:2
   f 'abcde'
abcde
abcd 
abc  
ab   
a    
 bcde
 bcd 
 bc  
 b   
  cde
  cd 
  c  
   de
   d 
    e

Explanation

[:;#\.<@{."_1|.\."1^:2  Input: s
             |.\."1     For each suffix of s, reverse it
                   ^:2  Repeat that twice to create all exploded substrings
   #\.                  Get the length of each suffix. This is
                        used to make the range [len(s), len(s)-1, ..., 1]
        {."_1           For each value in the range, take that many strings from
                        the list of exploded substrings. This avoids blank substrings
      <@                Box each set of strings
[:;                     Unbox and join the strings together and return

Answer 22

Java, 138 bytes

String e(String s){int l=s.length(),a=0,i,j;for(;++a<l;)for(i=0;i<=l-a;){s+="\n";for(j=0;j++<i;)s+=" ";s+=s.substring(i,i+++a);}return s;}

Formatted:

String e(String s) {
    int l = s.length(), a = 0, i, j;
    for (; ++a < l;)
        for (i = 0; i <= l - a;) {
            s += "\n";
            for (j = 0; j++ < i;)
                s += " ";
            s += s.substring(i, i++ + a);
        }
    return s;
}

Answer 23

Pyke, 15 bytes

QlFUQRd:DlRF2h<

Try it here!

Assumes array of padded strings is acceptable

Pads first and then chops.

Answer 24

Haskell, 65 bytes

(>>=zipWith((++).(`replicate`' '))[0..].init.tails).reverse.inits

It requires inits and tails from Data.List, though. To output it, add mapM_ putStrLn. to the front.

Relatively straightforward; the reverse is to make sure the original string is first.

GHCi> mapM_ putStrLn.(>>=zipWith((++).(`replicate`' '))[0..].init.tails).reverse.inits$"abcde"
abcde
 bcde
  cde
   de
    e
abcd
 bcd
  cd
   d
abc
 bc
  c
ab
 b
a
it :: ()
(0.02 secs, 0 bytes)

Answer 25

Ruby, 75 67 bytes

Anonymous function. Uses regex substitution to align the substrings. . is the filler character.

->s{(l=s.size).times{|i|(l-i).times{|j|puts s.tr(?^+s[j,i+1],?.)}}}

Answer 26

bash + GNU coreutils, 109 Bytes

l=${#1}
for i in `seq 0 $l`;{
for j in `seq $((l-i))`;{
for k in `seq $i`;{ printf ' ';}
echo ${1:i:j}
}; }

Maybe there is a shorter solution, but this is the best that came into my mind. Uniqueness of chracters does not matter here.

Answer 27

PHP, 151 chars

Ungolfed

<?php
$input = $argv[1];
foreach(str_split($input) as $p=>$letter)
{
    $spaces = str_repeat(" ", $p);
    echo $spaces.$letter."\n";
    $p++;
    for($i=$p;$i<strlen($input);$i++)
    {
        echo $spaces.$letter.substr($input, $p, $i)."\n";
    }
}
?>

Golfed

<?$c=$argv[1];foreach(str_split($c)as$d=>$b){$a=str_repeat(" ",$d);echo$a.$b."\n";$d++;for($e=$d;$e<strlen($c);$e++){echo$a.$b.substr($c,$d,$e)."\n";}}

Example

php explodesub.php 'abc'
a
ab
abc
 b
 bc
  c

Answer 28

C++, 145 Bytes

the first start parameter is used as input, console as output

#include<iostream>
#define f(y,b,d) for(int y=b;r[0][y];y++){d;}
int main(int,char*r[]){f(x,0,f(y,x+1,std::cout.write(r[0],y)<<'\n')r[0][x]=32)}

Answer 29

Python 2 (Ungolfed) 99 Bytes

t=raw_input()
l=len(t)
for j in range(l):
 for i in range(l):
  if i>=j:print j*' '+t[j:i+1]  

Result:

>>python codegolf.py
abc
a
ab
abc
 b
 bc
  c

>>python codegolf.py
abcdef
a
ab
abc
abcd
abcde
abcdef
 b
 bc
 bcd
 bcde
 bcdef
  c
  cd
  cde
  cdef
   d
   de
   def
    e
    ef
     f

>>python codegolf.py
lmnopqrst
l
lm
lmn
lmno
lmnop
lmnopq
lmnopqr
lmnopqrs
lmnopqrst
 m
 mn
 mno
 mnop
 mnopq
 mnopqr
 mnopqrs
 mnopqrst
  n
  no
  nop
  nopq
  nopqr
  nopqrs
  nopqrst
   o
   op
   opq
   opqr
   opqrs
   opqrst
    p
    pq
    pqr
    pqrs
    pqrst
     q
     qr
     qrs
     qrst
      r
      rs
      rst
       s
       st
        t