Finding Snakes in a Matrix Challenge

Given a binary matrix and a binary string, determine if that binary string can be found starting at any point in the matrix and moving in any direction at any subsequent point to form the binary string. That is, can the string be found folded up however inside the matrix?

The string can only be folded at 90 degrees or 180 degrees (edge connections; Manhattan Distance 1) and cannot overlap itself at any point.

Example

Let's take the following example:

Matrix:

010101
111011
011010
011011

Snake: 0111111100101


This is a truthy test case. We can see the snake folded up in the following position:

0-1 0 1 0 1
  |
1 1 1-0 1 1
  | | |   |
0 1 1 0-1-0
  | |
0 1-1 0 1 1


Rules


Standard Loopholes Apply  
You may take the length of the string and the width and height of the matrix as input if you'd like  
You may take the binary matrix and the binary string as a multiline string/array of strings/newline-joined string/anything else-joined string and a string  
You may take the dimensions as a flat array instead of several arguments    
Your program must finish for any 5 x 5 matrix with any string of up to length 10 in under a minute


Limitations


The matrix is not necessarily square  
The string will be non-empty  
The string can be length-1  
The string will not contain more squares than available (that is, len(string) &lt;= width(matrix) * height(matrix)


Test Cases

Truthy

01010
10101
01010
10101
01010

0101010101010101010101010



01110
01100
10010
10110
01101

011111000110100



0

0



10
01

1010



100
010
001

100010001


Falsy

00000
00000
00000
00000
00000

1



10101
01010
10101
01010
10101

11



100
010
001

111



10001
01010
00100
01010
10001

1000100010001000101010100
Python 2, 275 271 264 249 bytes


Saved four bytes by replacing -1 with H and removing one slicing operation ([:]).
Saved seven bytes thanks to Halvard Hummel; removing yet another slicing operation ([:]), using multiple-target assignment to give a visited entry a value v not in "01" (S=S[1:];M[y][x]=H; -> S=M[y][x]=S[1:];) and switching from a ternary if/else to a simple logical or (any(...)if S else 1 -> not S or any(...)).
If you somewhat extend your definition of truthy and falsey, you could allow this 257 byte long solution. It raises an exception (ZeroDivisionError) when the snake is found and returns an empty list ([]) when there is no snake to be found, which are two distinct behaviours.
Saved fourteen bytes thanks to user202729; golfing two array deep copies
Saved a byte; golfed not S or to S&lt;[1]or ~ S==[]or.




lambda M,S,w,h:any(H(eval(`M`),S,w,h,x,y)for y in range(h)for x in range(w)if S[0]==M[y][x])
def H(M,S,w,h,x,y):S=M[y][x]=S[1:];return S&lt;[1]or any(H(eval(`M`),S,w,h,x+X,y+Y)for X,Y in[(~0,0),(1,0),(0,~0),(0,1)]if~0&lt;x+X&lt;w&gt;0&lt;=y+Y&lt;h!=S[0]==M[y+Y][x+X])


Try it online!

Explanation

Lambda function which takes in the matrix as a two-dimensional list of strings (either "0" or "1"), the snake as a one-dimensional list and the matrix dimensions as two integers.
The lambda function searches the matrix for entries that match the snake's first element. For every found match, it calls H with a deep copy of the matrix, no copy of the snake, the matrix dimensions and the match's position.  

When H is called, it removes S' first entry and sets the given position's matrix entry to something else than "0", "1". If S' length is zero, it returns True; as it calls itself recursively, the snake was found somewhere in the matrix.
If S' length is non-zero, it loops through the four cardinal directions, tests if that position is in the matrix, compares the matrix' element at that position with the first element of S and -- if it matches -- calls itself recursively.
H's return values are funneled up the stack frames, always checking if at least one function found a possible snake.

Formatted Output

I have augmented my program to also output the path the snake slithers (if there is one). It uses the same ASCII output design as the question. TIO link.