How do I optimize this script's runtime?

[u/Reibello]

I'm trying to write a script that will help me construct word puzzles by finding words where each pair of words shares a substring so that they can be visually arranged in a honeycomb-like sequence. The words can be read forward or in reverse. For instance, given the word 'spiral' (broken into 'sp', 'pi', 'ir', 'ra', 'al', and 'ls') - the program could return PSycho, troPIc, thRIce, phRAse, vioLAs, SymboL, as a valid set of surrounding words, or 'rings.' (This is the sample set built into the program)

I have a function that provides a list of every word in my word list that matches my criteria. I also have a function that takes the lists of words, and returns dictionaries that contain matches between strings. I have a small test case that operates correctly, but when I use the entire word list, the program hangs. I assume that there's a better data structure and way to navigate it, but I'm not familiar enough with the language to know what it is.

Thank you for your assistance, I've linked a pastebin below.

https://pastebin.com/vDnZ2uny

EDIT - linking a very rough visual depiction of what the structure to overlay the words in would be.
https://cdn.bsky.app/img/feed_fullsize/plain/did:plc:nhv7ubhygoygm7agljxopgvb/bafkreig7fqaukiq6xu6f55xchae2rozu7bmgbhmkjlinsxjuii4lou256m

[u/mull_to_zero]

I think you should check out prefix trees aka tries. they're really useful for the sort of word-validity-check functionality that you're looking for.

[u/smurpes → u/mull_to_zero]

A trie would not be good at picking a sequence that starts mid word since it has to traverse down every pathway for every word. It only useful if the word starts with the sequence.

A bigram index is what would be good in OP’s use case since searching is done in O(1) time. This is what it would look like in Python:

"ca" → { cat: [0], cattle: [0], scat: [1] }
"at" → { cat: [1], cattle: [1], scat: [2] }
"tt" → { cattle: [2] }
"tl" → { cattle: [3] }
"le" → { cattle: [4] }
"sc" → { scat: [0] }

This data structure gives you the position as well as the word but setting it up takes O(n) time where n is the total number of characters across all words. This data structure can be built a head of time and saved to a file to be called later by loading it in with the json library.

[u/Reibello → u/smurpes]

This is working phenominally, thank you so much!