CS Theory Overflow

đã mở cho công chúng, các bạn có câu hỏi gì về các đề tài nghiên cứu liên quan đến lý thuyết máy tính có thể đặt ở đó. Nhớ rằng, giống như MathOverflow, cstheory dành cho các câu hỏi nghiên cứu chứ không phải để hỏi bài tập thiết kế thuật toán.

Một câu hỏi thú vị từ cstheory:

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPP and SSISI. Let me call a string square if it is a shuffle of two identical strings. For example, ABCABDCD is square, because it is a shuffle of ABCD and ABCD, but the string ABCDDCBA is not square.

Is there a fast algorithm to determine whether a string is square, or is it NP-hard? The obvious dynamic programming approach doesn’t seem to work.

Even the following special cases appear hard: (1) strings in which each character appears at most four times, and (2) strings with only two distinct characters.