UVa 10941

From Algorithmist
Jump to navigation Jump to search

10941 - Words Adjustment[edit]

Summary[edit]

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.

Explanation[edit]

The problem can be solved by BFS. The state in BFS is the unadjusted suffix of the longer of the two words.

Trivia[edit]

The original problem by Wojciech Rytter was offered at Polish Olympiad in Informatics 1995/1996.

Input[edit]

2
abba
ab
4
baaabad
aa
badccaa
cc
a
ab
4
bb
ab
ba
aa

Output[edit]

5
-1

More test cases are available here.