A fold of a finite string S over a given alphabet is an embedding of s in some fixed infinite grid, such as the square or cubic mesh. The score of a fold is the number of pairs of matching string symbols which are embedded at adjacent grid vertices. Folds of strings in two-and three-dimensional meshes are considered, and the corresponding problems of optimizing the score or acheiving a given target score are shown to be NP-hard.
展开▼
