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

Задача "строки-близнецы"
Автор igor.pisarev, 11 лет назад, По-русски

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

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

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

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

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

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

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    → Ответить
»
11 лет назад, # |
← 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.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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"

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

      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)

      edit: fixed a bug in pseudocode

      edit: I'm wrong, sorry.

      → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
← Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

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

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить