I Solved this problem, by transforming x and y into every system and search for the longest common substring.
But I am interested in another Ideas, better than mine, except brute force.

it isn't necessary to search LCS (O(|x|*|y|)), you can check only what y is subsequence of x, so it will be O(|x|+|y|)

Edited by author 30.08.2009 16:00

Verification of this fact is O(log(max(x,y)))

base = 2..1000 bruteforce,  base > 1000  think a little :))