Searching subsequences

AbstractWe define the directed acyclic subsequence graph of a text as the smallest deterministic partial finite automaton that recognizes all possible subsequences of that text. We define the size of the automaton as the size of the transition function and not the number of states. We show that it is possible to build this automaton using O(n log n) time and O(n) space for a text of size n. With this structure, we can search a subsequence in logarithmic time. We extend this construction to the case of multiple strings obtaining a O(n2 log n) time and O(n2) space algorithm, where n is the size of the set of strings. For the later case, we discuss its application to the longest common subsequence problem