I have an idea to this question, but not time to code. Basically like this.
Calculate the KMP look_up table for each words, we can get the shortest string prefix to add this word to be palindrome, actually it's shortest palindrome question. Time complexity (O(n)) Space complexity (O(n));
Create a trie tree for all words, search the prefix from tries tree, Time Complexcity O(k).
special case, the prefix actually is the prefix and prefix + (0 to n) the first letter of words. So tries tree search is non-standard.
I tried Trie structure.
Putting words in Trie takes a long time O(nk), search words (your step 2) take a long time too O(nn*m (m<<k)), all this add up make the solution not as fast as you expect.
It is a lot faster than the brute force method. But much slower than the HahsMap method in a hot posts. And my code still ETL.....
Hopefully you can come up with a much better solution...