Parsing with a finite dictionary

We address the following issue: given a word w∈A* and a set of n nonempty words X, how does one determine efficiently whether w∈X* or not? We discuss several methods including an O(r×|w|+|X|) algorithm for this problem where r⩽n is the length of a longest suffix chain of X and |X| is the sum of the lengths of words in X. We also consider the more general problem of providing all the decompositions of w in words of X.