Smallest Word Search Puzzle

A word search is a matrix of letters as defined in Word Search Puzzle Generation. For a word search to contain a word, it means that that word appears somewhere in the matrix horizontally, vertically, or diagonally.

Your task is to write a program that takes a list of strings and outputs the dimensions of the smallest-area word search that contains those strings.

Specifications

You can assume the word search and the input strings consist of only lowercase ASCII letters.
You can output the dimensions in either order (y x instead of x y) because it doesn't matter to the word search.
This is code-golf, so the shortest valid solution (in bytes) wins.

Test Cases

word                     -> 4 1
hello, e                 -> 5 1
hello, f                 -> 6 1
small, llama             -> 8 1
words, other             -> 5 2
words, order, about, orb -> 5 3

Esolanging Fruit

Posted 2017-02-21T22:26:32.213

Reputation: 13 542

5I'm not convinced that makes a meaningful difference? Do you have any reason to suspect any algorithm that would be competitive here and not if you had to print it? – FryAmTheEggman – 2017-02-21T23:44:44.387

Actually, there's a fairly major difference: that challenge asked for squares, this one for rectangles, and that may well make a large difference. If not for that, though, I'd call it a duplicate; the difference in output format might change which language wins, but it's unlikely to change the non-output part of the algorithms. – None – 2017-02-22T06:06:33.207

None of the test cases include diagonals, you should probably add one for that. – ETHproductions – 2017-02-22T13:31:18.180

1Wouldn't hello, f be 6 1 ? 6x1 is smaller than 5x2 – NibblyPig – 2017-02-22T14:48:17.273

@SLC Yes, edited. – Esolanging Fruit – 2017-02-23T02:28:31.820

This is till a dupe as trivial edits to get an answer – Christopher – 2017-02-23T03:32:21.357

@ChristopherPeart as ais523 pointed out, that challenged asked strictly for square matrices, while this one asked for arbitrary rectangles, so algorithms that worked for that challenge might not work for this one. That said, I suppose it's similar enough that it might be marked as a duplicate. – Esolanging Fruit – 2017-02-23T03:42:26.683

³L jelly 2 bytes words must just be put in as one long word. :P – Christopher – 2017-02-23T03:44:28.020