Compact directed acyclic word graphs for a sliding window

Suffix trees are a well-known and widely-studied data structure highly useful for string matching. The suffix tree of a string ω can be constructed in O(n) time and space, where n denotes the length of ω. Larsson achieved an efficient algorithm to maintain suffix trees for a sliding window. It contributes to prediction by partial matching (PPM) style statistical data compression scheme. Compact directed acyclic word graphs (CDAWGs) are a more space-economical data structure for indexing strings. In this paper we propose a linear-time algorithm to maintain CDAWGs for a sliding window.