Summary: In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in [L. Parida, I. Rigoutsos and D. Platt, Lect. Notes Comput. Sci. 2089, 131–142 (2001; Zbl 0990.68536); N. Pisanti, M. Crochemore, R. Grossi and M.-F. Sagot, Lect. Notes Comput. Sci. 2747, 622–631 (2003); J. Pelfrêne, S. Abdeddaïm and J. Alexandre, Lect. Notes Comput. Sci. 2676, 328–347 (2003)] its output-polynomial time computability has been still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length \(n\) in \(O (n^{3})\) time per motif with \(O (n)\) space, in particular \(O (n^{3})\) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lower bound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach. The results of the computational experiments show that our algorithm can be applicable to huge string data such as genome data in practice, and does not take large additional computational cost compared to usual frequent motif mining algorithms.