is FIND WORDS in P?

FIND WORDS is the following decision problem:

Given a list of words L and a Matrix M, are all words in L also in M?
The words in M can be written up to down, down to up, left to right, right to left, diagonal-left-up, diagonal-left-down, diagonal-right-up and diagonal-righ-down.
To be specific this is the classic game that can be found in the puzzling week: FIND WORDS

Now this decision problem clearly is in NP
because, given a certificate with the positions of the words in the matrix (indexes), a verifier can check it in polynomial time.

My question is this: are we aware of Turing Machines that decide this language in polynomial time?

Your language is in P. Suppose that the matrix is $n\times n$ and that the words have total length $\ell$. Each word can start at at most $n^2$ positions and be written in $O(1)$ many orientations, for a total of $O(n^2)$ possible placements. Checking each one costs at most $O(m)$, where $m$ is the length of the word. In total, we obtain an algorithm whose running time is $O(\ell n^2)$, which is quadratic in the input length.

Using a trie or similar data structure, you can probably improve this to linear time $O(n^2 + \ell)$.

StackExchange Computer Science Q#112065, answer score: 16