Сложение в строк С++ — скандалы, интриги, расследования.

Блог пользователя Rap_Promoter

Автор Rap_Promoter, 11 лет назад, По-русски

На предыдущем контесте (Round #177, div.2) случилось страшное, однако для меня обыденное — задача С, по которой я сделал шесть взломов у меня упала по TL. Вот код.

Я, перечитав код, начал пенять на сложение строк. Скажите, это оно виновато в моем горе, или я неправ, и ошибка в другом? Если это сложение строк, то скажите, почему оно так долго работает?

Спойлер: массив "a" не имеет применения в данном коде.

UPD: операция "+" для строк для работает за линию.

Будьте бдительны!

-4

Rap_Promoter
11 лет назад
13

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

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

savinov

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

Тут написано "Complexity: Unspecified, but generally up to linear in the new string length."

→ Ответить

Rap_Promoter

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

-7

Это кошмар и ужас. Но зато теперь буду знать. Спасибо.

→ Ответить

Hohol

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

Это сложность выполнения одной операции. Амортизированная сложность кучи сложений будет видимо близка к O(итоговая длина).

→ Ответить

savinov

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

s = (char)('a' + i) + s;

Вот здесь это точно будет квадрат.

→ Ответить

Avitella

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

Это относится к тем же приколам, что бывают с векторами. То есть в случае, когда нужно сделать реаллокацию, сложность действительно будет O(new_length). В остальных случаях O(1). То есть амортизированная сложность в итоге будет O(length).

→ Ответить

Avitella

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

← Rev. 2 →

И действительно:

for (int i = k - 1; i > 1; --i)
    s = (char)('a' + i) + s;
for (int i = 0; i <= n; ++i)
    s1 = s1 + (char)('a' + (i % 2));

В случае строк посмотрим на оператор +:

template<typename _CharT, typename _Traits, typename _Alloc>
  basic_string<_CharT, _Traits, _Alloc>
  operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
  {
    basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
    __str.append(__rhs);
    return __str;
  }

И на оператор +=:

basic_string&
operator+=(const basic_string& __str)
  { return this->append(__str); }

То есть ваш код работал за квадрат, так как создавался объект на основе первой строки, затем уже к нему добавлялась вторая строка. В случае строк лучше делать +=. Так как не создаются объекты, если они нам не нужны, а работает, как push_back в массиве.

→ Ответить

Hohol

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

Странно пенять на операцию "+=", которой в вашем коде вообще нет. Эта операция работает быстро. У вас же каждый раз выполняется простое присваиваение s = s+один_символ. Это, конечно, работает долго.

→ Ответить

Rap_Promoter

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

-8

Да, "+=" было странной опиской, спасибо

→ Ответить

caustique

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

+10

Всю жизнь строки складывал так же, как ты. Спасибо за подсказку, больше так делать не буду :3

→ Ответить

dalex

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

Понятно же, что s = t + s будет работать за квадрат. Нельзя просто так взять и дописать элементы спереди. Если уж очень надо, то deque<char> какой-нибудь поможет, наверно.

→ Ответить

Avitella

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

← Rev. 2 →

Ну такого там нет. Там все-таки s = s + t, но только суть от этого не меняется. Не знаю, как в джаве, но в плюсах точно происходит создание того, что я описал выше. В принципе могу выложить сюда и код того, как работает append, но это вряд-ли целесообразно, у всех он и так есть :)

UPD. s = t + s там тоже есть, но таких операций не более, чем k. То есть мало.

→ Ответить