Words distinguished by their subwords

Abstract:

We present an O(|A|(|x₁|+|x₂|)) algorithm to find a shortest word which divides x₁ iff it does not divide x₂, where x₁ and x₂ are words over the alphabet A. Based on the length of such a word an ultra-metric distance on A^* can be defined. The algorithm can be transformed to work in time and space O(|A|+|x₁|+|x₂|).

Note 1: We say that a word x divides a word y if x is a subsequence of y.

Note 2: This is the second half of the "Dois algoritmos estupidamente eficientes" I began to present in August.