10941 - Words Adjustment
Given two words , , and a dictionary with a number of words, it is allowed to append to and any words from the dictionary. Determine the minimum number of words that must be appended to make and equal.
The problem can be solved by BFS. The state in BFS is the unadjusted suffix of the longer of the two words.
The original problem by Wojciech Rytter was offered at Polish Olympiad in Informatics 1995/1996.
2 abba ab 4 baaabad aa badccaa cc a ab 4 bb ab ba aa
More test cases are available here.