Check if B is composed of substrings of A of length n

Question

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 code-golf, so the shortest code in bytes wins

Answer 1

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

Answer 2

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
}

Answer 3

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

Answer 4

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

• Truthy case

• Another test

Answer 5

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!

Answer 6

K (ngn/k), 32 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?)

Answer 7

Charcoal, 31 bytes

Ｎθ⬤ζ⊙Ｅ⌊⟦θ⊕κ⟧✂ζ⁻κλ⁺⁻κλθ¹∧⁼Ｌλθ№ηλ

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

Ｎθ                              Input `n` as a number
   ζ                            Input `B`
  ⬤                             All characters must match
        θ                       Input `n`
          κ                     Current index
         ⊕                      Incremented
      ⌊⟦   ⟧                    Minimum
     Ｅ                          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
                         Ｌ      Length
                        ⁼       Equals
                           θ    Input `n`
                       ∧        Logical And
                              λ Current string
                            №   Contained in
                             η  Input `A`
                                Implicitly print

Alternative solution, also 31 bytes:

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

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

Ｎθ                              Input `n` as a number
   ζ                            Input `B`
  ⬤                             All characters must match
         ⁰                      Literal zero
           κ                    Current index
          ⁻                     Minus
             θ                  Input `n`
            ⊖                   Decremented
       ⌈⟦     ⟧                 Maximum
                 κ              Current index
                    ζ           Input `B`
                   Ｌ            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:

ＮθＦ⁻Ｌη⊖θＦ⌕Ａζ✂ηι⁺ιθＦθ⊞υ⁺κλ¬⁻Ｅζκυ

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

Ｎθ

Input n.

Ｆ⁻Ｌη⊖θ

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

Ｆ⌕Ａζ✂ηι⁺ιθ

Loop over all matches of each substring in input B.

Ｆθ⊞υ⁺κλ

Record the index of each character in each match.

¬⁻Ｅζκυ

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

Answer 8

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)

Answer 9

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.

Answer 10

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

Answer 11

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.

Answer 12

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.

Answer 13

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.

Answer 14

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?

Answer 15

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!