12
\$\begingroup\$

Given two strings \$ A \$ and \$ B \$ and a positive integer \$ n \$, determine whether \$ B \$ is composed entirely of (possibly overlapping) strict substrings of \$ A \$ of a length of at least \$ n \$.

Test cases

n  A               B               Output
-----------------------------------------
2  abcdefg         bcabcdebcdef    True
2  abcdefg         cdabfg          True
4  abracadabra     abrabrabrabra   True
1  abcdefg         ddbfeg          True
2  ab              abab            True
2  bb              bbbbb           True
5  abcdefghijklmn  defghabcdefghi  True
2  abcdefg         hijklmn         False
3  abcdefg         bcabcdebcdef    False
2  abcdefg         ddabfg          False
2  ab              aba             False
2  abcdefg         a               False
4  abracadabra     brabrabrabra    False
6  abcdefghijklmn  defghabcdefghi  False

Rules

  • You may assume that both \$ A \$ and \$ B \$ are non-empty; \$ n \ge 1 \$; and \$ A \$ has a length of at least \$ n \$
  • You may choose to operate on arrays with elements of any data type or set of values, rather than strings, as long as there are at least 8 distinct values for that element type
  • You can output using truthy or falsey values, or any two other disjoint sets of values, to indicate a true or false result
  • You may use any sensible I/O format
  • Standard loopholes are forbidden
  • This is , so the shortest code in bytes wins
\$\endgroup\$
7
  • \$\begingroup\$ Sandbox \$\endgroup\$ – pxeger Mar 26 at 15:24
  • 6
    \$\begingroup\$ The fact that the last case is supposed to be false is a weird edge case. The empty string B is made of exactly 0 substring of any A, for any n. \$\endgroup\$ – Arnauld Mar 26 at 16:10
  • \$\begingroup\$ @Arnauld I'll say no empty strings for A or B then \$\endgroup\$ – pxeger Mar 26 at 16:27
  • 1
    \$\begingroup\$ If n=2, a=abzaxy, and b=xyzab, should that return true or false? I'm guessing the "possibly overlapping" means that is true.... though I think the problem is more interesting if that one is supposed to be false. \$\endgroup\$ – Jonah Mar 27 at 17:55
  • \$\begingroup\$ @Jonah yes, that should be true \$\endgroup\$ – pxeger Mar 27 at 20:14

15 Answers 15

6
\$\begingroup\$

Excel, 114 bytes

A nice low bar to start with.

=LET(x,SEQUENCE(LEN(C1)),t,TRANSPOSE(x),AND(MMULT((x<t+A1)*(x>=t),IFERROR(FIND(MID(C1&REPT(" ",A1),x,A1),B1),0))))
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Excel is a Lisp dialect with commas and opening parens in the wrong place, and a sprinkling of infix? :) \$\endgroup\$ – Kaz Mar 28 at 20:47
  • \$\begingroup\$ It's been a while since I've done any Lisp. It looks like it's moving that direction, especially with the addition of the LAMBDA function in the future. \$\endgroup\$ – Axuary Mar 29 at 0:12
5
\$\begingroup\$

R, 117 109 bytes

Edit: -8 bytes thanks to some nice golfing by Robin Ryder

function(n,a,b,p=nchar(b),s=n:p-n+1,S=sapply)p>=n&all(1:p%in%S(s[S(substring(b,s,s+n-1),grepl,a)],`+`,1:n-1))

Try it online!

Ungolfed

b_all_substrings_of_a=
function(n,a,b){
  r=substring(b,s<-seq(nchar(b)-n+1),s+n-1)  # r=all length-n substrings of b
  m=sapply(r,grepl,a)                        # m=check whether each of r is found in a
  i=sapply(s[m],`+`,1:n-1)                   # i=for each r that was in a, make a sequence length n starting at r
                                             #   (so i is the indices of the letters in b in each match)
  nchar(b)>=n                                # finally, check that b is at least n characters long
    &all(1:nchar(b)%in%i)                    # and that all the letters in b belong to a match to a
}

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

Husk, 12 bytes

`-ŀ¹×+ŀ⁵W€²X

Try it online! (or try some true examples or some more false examples)

Returns a list of the letters of b that aren't part of a length-n substring of a (so, empty list corresponds to 'b is composed of substrings of a', non-empty list indicates that this isn't the case).
This is loosely a port of my R answer.

How?

 `-ŀ¹×+ŀ⁵W€²X   # full program with:
                # arg1 (⁵) = n
                # arg2 (²) = a
                # arg3 (¹) = b
            X   # get all substrings of length n from string b; 
         W      # now get indices of 
          €²    # the ones that are in a;
     ×+ŀ⁵       # add 0..n-1 to each of them, 
 `-ŀ¹           # and output any of 1..length(b) that aren't among these
\$\endgroup\$
3
  • \$\begingroup\$ Why is arg1 rather than ³? \$\endgroup\$ – caird coinheringaahing Mar 26 at 22:09
  • 2
    \$\begingroup\$ @ChartZBelatedly - Er, it's a bit non-intuitive at first... Husk program arguments are numbered in reverse, using even numbers starting at zero: so with 3 program args, arg1 is 4, arg2 is 2, and arg3 is 0. But... if we use the odd numbers, then an additional copy is automatically added to the end of the program (so that we don't need to waste a character specifying it twice). So, in this case, arg3 and arg1 are both appended to the end of the program to be used by X (and so use odd-numbered indices), and arg2 is only used once (so gets the even-numbered index). \$\endgroup\$ – Dominic van Essen Mar 26 at 22:13
  • \$\begingroup\$ @ChartZBelatedly - probably a better explanation here \$\endgroup\$ – Dominic van Essen Mar 26 at 22:15
4
\$\begingroup\$

Japt -!, 13 15 bytes

Vã l¨W Ô£=eX0ÃU

Try it

  • 1st input U : string B
  • 2nd input V : string A
  • 3rd input W : minimum length
  * fixed a bug
    Vã        - all substrings
    l¨W       - filter out shorter than W
    Ô      * reverse to remove longer first
    £= ... Ã  - map by reassigning U
    eX          : remove all occurrences
    0      * and put a '0'
    U + flag ! to print true if U is empty
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 102 bytes

Returns a Boolean value.

(n,a,b)=>[...b].every((_,i,A)=>A.some((_,j)=>!A.every((_,k)=>i<j|i>k|++k-j<n|!a.match(b.slice(j,k)))))

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I believe this can be shorter now I've changed the rules on empty strings \$\endgroup\$ – pxeger Mar 26 at 16:30
  • \$\begingroup\$ @pxeger Yes. :-) Updated. \$\endgroup\$ – Arnauld Mar 26 at 16:35
3
\$\begingroup\$

K (ngn/k), 31 29 bytes

{i~?,/(x'i:!#z)@&~^(x'y)?x'z}

Try it online!

Makes heavy use of int'list to build sliding windows of the input strings. x is N (the minimum length of the substrings), y is A (the source of the substrings), and z is B (the string to check).

  • (x'y)?x'z find the beginning indices of where each N-length substring from A occurs in B (e.g., "abra" occurs in "abrabrabrabra", with each match beginning at indices 0, 3, 6, and 9. No other index in B is the beginning of a 4-length substring from "abracadabra")
  • @&~^ apply using indices corresponding to matches (e.g., 0 3 6 9)
  • (x'i:!#z) build sliding windows of the range from 0..len(B), storing this range in variable i; when indexed into, this returns the indices in B that are part of some valid substring from A (e.g., (0 1 2 3;3 4 5 6;6 7 8 9;9 10 11 12))
  • ?,/ flatten the distinct indices, as there can be overlaps (e.g., 0 1 2 3 4 5 6 7 8 9 10 11 12)
  • i~ are all characters in B accounted for? (i.e., are they part of a N-length substring from A?)
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 31 bytes

Nθ⬤ζ⊙E⌊⟦θ⊕κ⟧✂ζ⁻κλ⁺⁻κλθ¹∧⁼Lλθ№ηλ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for true, empty for false. Explanation:

Nθ                              Input `n` as a number
   ζ                            Input `B`
  ⬤                             All characters must match
        θ                       Input `n`
          κ                     Current index
         ⊕                      Incremented
      ⌊⟦   ⟧                    Minimum
     E                          Map over implicit range
             ζ                  Input `B`
            ✂         ¹         Sliced from
               κ                Outer index
              ⁻                 Minus
                λ               Inner value
                  ⁻κλ           To outer index minus inner value
                 ⁺              Plus
                     θ          Input `n`
    ⊙                           Any string satisfies
                          λ     Current string
                         L      Length
                        ⁼       Equals
                           θ    Input `n`
                       ∧        Logical And
                              λ Current string
                            №   Contained in
                             η  Input `A`
                                Implicitly print

Alternative solution, also 31 bytes:

Nθ⬤ζ⊙…·⌈⟦⁰⁻κ⊖θ⟧⌊⟦κ⁻Lζθ⟧№η✂ζλ⁺λθ

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

Nθ                              Input `n` as a number
   ζ                            Input `B`
  ⬤                             All characters must match
         ⁰                      Literal zero
           κ                    Current index
          ⁻                     Minus
             θ                  Input `n`
            ⊖                   Decremented
       ⌈⟦     ⟧                 Maximum
                 κ              Current index
                    ζ           Input `B`
                   L            Length
                  ⁻             Minus
                     θ          Input `n`
               ⌊⟦     ⟧         Minimum
     …·                         Inclusive range
    ⊙                           Any value satisfies
                          ζ     Input `B`
                         ✂      Sliced from
                           λ    Current value to
                             λ  Current value
                            ⁺   Plus
                              θ Input `n`
                       №        Contained in
                        η       Input `A`
                                Implicitly print

Alternative solution, also 31 bytes:

NθF⁻Lη⊖θF⌕Aζ✂ηι⁺ιθFθ⊞υ⁺κλ¬⁻Eζκυ

Try it online! Link is to verbose version of code. Explanation: Port of @DominicvanEssen's answer.

Nθ

Input n.

F⁻Lη⊖θ

Loop over the starting index of all substrings of length n in input A.

F⌕Aζ✂ηι⁺ιθ

Loop over all matches of each substring in input B.

Fθ⊞υ⁺κλ

Record the index of each character in each match.

¬⁻Eζκυ

Check that each index in input B was recorded at least once.

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

Retina, 35 bytes

~L$`.+$
v`(.{$&})(?=.$*$¶.$*\1)¶
^¶

Try it online! Takes newline-separated arguments in the order B, A, n but test suite splits on ,s for convenience. Explanation:

L$`.+$
v`(.{$&})(?=.$*$¶.$*\1)¶

Create a stage that matches overlapping substrings of length n from B that also appear in A and deletes any matching characters.

~`

Evaluate that stage on the original input.

Check that all the characters from B were deleted.

Example: If n is 4, then the generated stage is as follows:

v`(.{4})(?=.*¶.*\1)

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

Retina 0.8.2, 72 67 bytes

.+$
$*
^((?=((.)+)(.*¶.*\2.*¶(?<-3>1)+)$)(?=(?<-3>.)*).+(?=.*\4))+¶

Try it online! Takes newline-separated arguments in the order B, A, n but test suite splits on ,s for convenience. Explanation:

.+$
$*

Convert n to unary.

^(...)+¶

Ensure B matches...

(?=((.)+)

... a number of substrings...

(.*¶.*\2.*¶

... that appear in A, and...

(?<-3>1)+)$)

... are at least n in length...

(?=(?<-3>.)*)

... but might be more than n, so reset it to zero for the next loop...

.+(?=.*\4)

... and allow the substrings to overlap.

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

JavaScript (Node.js), 77 bytes

(n,A,B)=>[...B].every((c,i)=>B[i+n-1]&&~A.indexOf(B.substr(i,n))?k=n:--k,k=1)

Try it online!

Input n and two strings. Strings may only contains BMP characters, in UTF-16. (Most characters will fall into this part. Some emoji's and rare used Han characters may not be suitable here.) Output true vs. false.


JavaScript (Node.js), 68 bytes

(n,A,B)=>[...B].every((c,i)=>A.match((B+8).substr(i,n))?k=n:--k,k=1)

Try it online!

If we restrict the values of A, B to a small subset of characters. We can reduce more bytes here. Above 71 bytes code supports A, B with only "a"~"z" letters (as all testcases provided here).

\$\endgroup\$
2
  • \$\begingroup\$ You can limit the input to 1 ~ 9! The question says "You may choose to operate on arrays with elements of any data type or set of values as long as there are at least 8 distinct values for that element type", which I added specifically to allow tricks like this \$\endgroup\$ – pxeger Mar 27 at 11:50
  • \$\begingroup\$ @pxeger added another function supports only "a"~"z" letters. \$\endgroup\$ – tsh Mar 27 at 12:26
1
\$\begingroup\$

C, 200 bytes

main(int c,char*v[]){char*s,*t=v[3];int a=1,K=0,x,y,m=atoi(v[1]);X=strlen(v[2])-m+1,y=strlen(t)-m+1;while(a--){s=v[2];K=0;for(x=0;x<X;++x){if(!strncmp(s++,t,m)){a=m;K=1;}}++t;if(!--y)break;}exit(K);}

GNU compiler cries all the warnings but code is OK on most architectures.

\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Golf! Nice first answer. I'd suggest checking out the Tips for golfing in C page (in particular I think you can save a lot by submitting a function rather than a full program); Also you might want to add a link to Try It Online \$\endgroup\$ – pxeger Mar 27 at 17:15
  • \$\begingroup\$ On this site, it is perfectly fine that your code only works with certain compiler on certain platform. As long as there is one. You only need to specify the compiler / platform you are using. So for example, you may claim you are using "C (gcc)" instead of simply "C". \$\endgroup\$ – tsh Mar 29 at 4:02
1
\$\begingroup\$

J, 28 bytes

1 :'#\@]-.+/@E.&m\;@#(<\#\)'

Try it online!

This is an adnoun modifying A, and taking n and B as left and right arguments. Example usage:

2 ('abcdefg' f) 'bcabcdebcdef'   

Returns an empty list when true, a non-empty list when false.

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

C (gcc), 72 bytes

k;f(n,a,b)char*a,*b;{for(k=1;k=memmem(a,strlen(a),b,n)?n:k-1;b++);k=*b;}

Try it online!

Return zero if b meets requirements. Return non-zero values otherwise.

Check if n bytes starting from b (possibly including the NULL-terminated byte and garbage after it) is available in string a (without the NULL byte). If we failed to find out such a matching n times continuesly or at the beginning, we know b does not meet the requirement. We break the loop if this happened, and *b here will be non-zero. As there should not be NULL bytes in a, as long as we reached the NULL byte in b, the n times mismatch will be eventfully happened. But this time, *b would be zero.

According to the implementation of glibc, this function would be memory safe when n < 32 (as long as CHAR_BIT == 8). And once n >= 32 && CHAR_BIT < 10, it may failed by invalid memory access which access the memory after the NULL terminator of b.

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

Jelly, 13 bytes

ẇ⁹Ƥ⁵o¬{Ṛḣ¥Ƥ§Ạ

A full program accepting B n A that prints 1 if B is composable from substrings of length n (or more) of A, or 0 if not.

Try it online!

Or see a test-suite (Altered to a functional form & using the register, ®, populated with A in the footer.)

How?

ẇ⁹Ƥ⁵o¬{Ṛḣ¥Ƥ§Ạ - Main Link: B, n
 ⁹Ƥ           - for infixes (of B) of length n:
ẇ  ⁵          -   is a sublist of A?
    o         - logical OR (vectorised) with:
     ¬{       -   logical NOT B (a vector of zeros the same length as B)
                (o¬{ has the effect of adding n-1 zeros)
          Ƥ   - for prefixes:
         ¥    -   last two links as a dyad - f(prefix, n):
       Ṛ      -     reverse (the prefix)
        ḣ     -     head to length (n) (a no-op if less than length n)
           §  - sums
            Ạ - all non-zero?
\$\endgroup\$
0
\$\begingroup\$

Python 2, 94 bytes

n,a,b=input()
t=[0]*len(b)
for i in range(len(b)-n+1):
 if b[i:i+n]in a:t[i:i+n]=n*[1]
print t

The program prints a list containing 1's and/or 0's. A list containing all 1's is truthy and a list containing any 0's is falsey.

Try it online!

\$\endgroup\$

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.