Задача "строки-близнецы"

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
7	cnnfls_csy	3569
9	ecnerwala	3494
10	Um_nik	3396

№	Пользователь	Вклад
1	Um_nik	164
2	maomao90	160
3	-is-this-fft-	159
4	atcoder_official	158
4	cry	158
4	awoo	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	maroonrk	152

Привет!
Пытаюсь решить следующую задачу, найденную на одном из форумов:

Две строки могут быть перемешаны путем вставки символов первой строки между символами второй (с сохранением их порядка). Рассмотрим перемешивание двух одинаковых строк - близнецов.

Например, строка AAABAB может быть получена путем перемешивания двух строк AAB.

Дается строка, необходимо определить, могла ли она быть получена путем перемешивания двух некоторых строк-близнецов.  
(другими словами, можно ли вычеркнуть половину символов так, чтобы строки, образованные вычеркнутыми и оставшимися символами, совпадали)

Логичная предпроверка: необходима четность каждого символа (XOR всех символов == 0).
Далее, ничего не удается придумать, кроме полного рекурсивного перебора O(2^N) :(

Как можно решить задачу более эффективно?

def is_twin_shuffle(string g of length n): s = "" t = "" s_index = 0 for i from 0 to n-1: if s_index = length of s or g[i] != s[s_index]: s += g[i] if s_index == -1: s_index = 0 else: t += g[i] s_index += 1 return (s == t)

Комментарии (13)

Написать комментарий?

OutSide

11 лет назад, # |

← Rev. 2 →

UPD: не работает на тесте AABAAB

→ Ответить

igor.pisarev

11 лет назад, # ^ |

Если правильно понял, на тривиальном тесте AABAAB такое решение дает неверный ответ? Похоже, что в остальных случаях работает, доказать бы корректность.. :)

aquamongoose

← Rev. 3 →

-8

Note that the first letter of the given string also has to be the first letter of each twin. We can remove the first two copies of that letter, and then recurse. This should give an O(n) algorithm if implemented efficiently.

Edit: it appears this problem is NP-hard. My solution is wrong.

I've posted similar solution to the russian branch. But if I understand you correctly, your solution fails on the test "ABCCAB". Answer for this test is "no"

No, maybe I didn't explain my solution well enough. Here is pseudocode of my idea:

edit: fixed a bug in pseudocode

edit: I'm wrong, sorry.

dasko1

+24

You won't be able to solve this problem efficiently, unless P=NP. Link

Thank you for the link. Haven't found it, very interesting

Omelianenko

+13

N^2. Идем циклом от i=1 до n-n/2+1(строки нумеруются с 1). Вырезаем строку которая начинается в позиции i длинной n/2. Если после склейки оставшихся символом будет такая же строка, то ответ yes. Если в конце не нашло ответа то ответ no. Можно все делать посимвольно, тогда решение будет работать быстрее.

upd. Условия я читать не умею, не ту задачу делал.

Придумался контр-пример: AABBCC (решение не учитывает множественного вложения одной строки в другую)

BekzhanKassenov

-13

Ну все же не O(2^n), а C(n / 2, n). Просто в переборе, если взяли n/2 элементов, дальше не идем :). Небольшая оптимизация.

ilovealyona

то есть для строки AABBCC ответ утвердительный — зачеркиваем все символы на четных/нечетных местах?

Да, все так

ns_serg

upd. Удалено, не работает.

Блог пользователя igor.pisarev