文字列の結合(+=だと計算量が異なる?)
解決したいこと
文字列s,tを結合するときにt=t+sとt+=sとするのでは計算量が大きく異なるがそれはなぜですか?
競技プログラミングのZONeエナジー プログラミングコンテスト “HELLO SPACE”のD問題を解いていて発見しました。
以下には２つのコードがありますが、違いは39行目(t = t + s[i] なのか t += s[i] なのか)のみです。サイト上で実行していただけると計算時間が大きく異なっていることが確認できると思います。
該当するソースコード
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main()
{
string s;
cin >> s;
int n = s.size();
string t = "";
bool rev = false;
int t_size = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == 'R')
{
rev = !rev;
continue;
}
if (t_size == 0)
{
t = t + s[i];
t_size++;
}
else
{
if (!rev)
{
if (t[t_size - 1] == s[i])
{
t.erase(t_size - 1);
t_size--;
}
else
{
t = t + s[i];
t_size++;
}
}
else
{
if (t[0] == s[i])
{
t.erase(0, 1);
t_size--;
}
else
{
t = s[i] + t;
t_size++;
}
}
}
}
if (rev)
reverse(t.begin(), t.end());
cout << t << endl;
}
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main()
{
string s;
cin >> s;
int n = s.size();
string t = "";
bool rev = false;
int t_size = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == 'R')
{
rev = !rev;
continue;
}
if (t_size == 0)
{
t = t + s[i];
t_size++;
}
else
{
if (!rev)
{
if (t[t_size - 1] == s[i])
{
t.erase(t_size - 1);
t_size--;
}
else
{
t += s[i];
t_size++;
}
}
else
{
if (t[0] == s[i])
{
t.erase(0, 1);
t_size--;
}
else
{
t = s[i] + t;
t_size++;
}
}
}
}
if (rev)
reverse(t.begin(), t.end());
cout << t << endl;
}
0
