内容別リスト/変数とデータ構造/string型 - 競技プログラミング用 知識集積所

---

雑な説明

文字列型変数。

レベル

ABCのA問題レベル。

詳細な説明

文字列型。
自由な文字数の言葉（半角英数字のみ）を入れることができる。
ダブルクオーテーション" "を使うことでstring型として扱われる。

1つの変数のようにも扱えるが、実際の中身はchar型変数の集合体である。
コードを書くときは2種類の見方を上手に切り替えながら行う必要がある。

宣言と初期化

宣言だけする場合

string s;                   // 宣言だけで実は空文字列""で初期化される

代入で初期化する場合

string s = "Hello World!";  //固定値で初期化
string s = string(5,'a');   //文字数と文字種で初期化、この場合は"aaaaa"となる
string s = t;               //他の変数（文字列型）で初期化

コピーコンストラクタで初期化する場合

string s("Hello World!");   //固定値で初期化
string s(5,'a');            //文字数と文字種で初期化、この場合は"aaaaa"となる
string s(t);                //他の変数（文字列型）で初期化

可能な演算

基本的なもの

i文字目を参照 .at(i) または [i]

例えば

s.at(3)

と書けば、「sという文字列の3文字目」というchar型変数であるかのように扱える。
ただし、コンピューター的には文字数は0から始まるため、"abcde"の3文字目は'd'であることに注意。
以後の計算でも全て同様。

s[3]

と書いてもほぼ同じ。
違いは、範囲外（3文字しかないのに5文字目を参照しようとする）などしたときの挙動の違い。
前者はエラーしてくれるのでバグの修正がしやすいがコードがちょっと見にくい。
後者はちょっとコードが見やすいが、エラーせず強引に実行して変な結果を出すだけなのでバグの修正が大変。
急いでバグ修正する必要がある競プロでは.at(i)を使う方が無難。

長さの取得 .size() または .length()

s.size()

で文字列sの長さをsize_t型で取得できる。
size_t型は扱いの注意点も多いので、取得したらそのままint型変数に一度代入してしまうのも1つの手。

代入 =

s=t; で、変数sの中身をtという値に書き換える。
数学とは違い、左右を逆にして t=s; と書くと意味が変わるので注意。

連結 +

s+tで、sにtを連結する。
tはchar型でもいい。

空判定 .empty()

s.empty()で、sが空っぽかどうかをbool型で返す。
結果自体はs==""とかs.size()==0と書くのと変わらない。
一応、.empty()が最も高速らしいが、誤差レベルなので書きやすさ優先で選んでよし。

コンストラクタ string(文字数,文字) （B問題レベル）

string(5,'a')と書くと、'a'を5文字並べた文字列"aaaaa"を意味する。
5文字くらいなら直接書いた方が早いが、100文字並べる場合などにはコンストラクタで書いた方が便利。

メモリ確保 .reserve(文字数) （C問題レベル）

s.reserve(100000)と書くと、100000文字分のメモリを確保する。
確保できない場合は、今のうちに100000文字確保できるところにデータをお引越ししてくれる。
後で文字をどんどん追加して長くなっていく場合に、可能性のある最長文字数以上に確保しておくとよい。

別にこれをやらなくても足りなくなった時点で自動的にメモリが空いてるところにお引越ししてくれるため、必須ではない。
とはいえ、99999文字まで書いたところで「メモリの連続空きスペースが足らなくなったので、この99999文字全部お引越ししまーす」という不要な処理が発生してTLEしたら悲しい。

文字列編集系（全体的にB問題レベル）

先頭取得 .front()

s.front()で先頭の文字をchar型で参照する。
……普通にs.at(0)でいい気が。

末尾取得 .back()

s.back()で末尾の文字をchar型で参照する。
文字列の長さが途中で変化するような場合には便利。

部分文字列取得 .substr(開始位置,文字数) または string(イテレータ1,イテレータ2)

s.substr(4,2)なら、4文字目からの2文字を別の文字列として取得する。
参照ではないので、substr()したものを変更しても、元の文字列には何も起こらない。
string(s.begin()+4,s.begin()+5)でも同じことができる。

末尾挿入 .push_back(文字)

s.push_back('x');なら文字列の最後に'x'を1文字追加する。
……普通に+='x'でいい気が。
また。vector（未作成）とは異なり.emplace_back()は使えない。

末尾削除 .pop_back()

s.pop_back();で、sの最後の1文字を削除する。

途中挿入 .insert(イテレータ,文字)

s.insert(itr,'a');で、itrの位置に'a'という文字を挿入する。

途中削除 .erase(開始位置,文字数) または .erase(イテレータ)

s.erase(4,2);なら、4文字目からの2文字を削除する。
s.erase(4)のように文字数を省略すれば、4文字目から後ろ全てを削除する。
引数をイテレータ（未作成）にした場合は、その場所の文字を削除する。

全削除 .clear()

s.clear();でsを空文字列にする。
……普通にs="";でいい気が。

置換 .replace(開始位置,文字数,置換文字列)

s.replace(3,2,"abc");なら、3文字目から2文字を削除し、代わりに"abc"をそこに入れる。

サイズ変更 .resize(文字数,文字)

文字列の長さを変更する。
短くする場合は後ろを削除、長くする場合は後ろを指定文字で埋める。
例えばsの中身が"abcde"である場合、s.resize(3)なら"abc"に、s.resize(8,'x')なら"abcdexxx"になる。

交換 .swap(別の文字列変数)

s.swap(t);で、sとtの中身が入れ替わる。
swap(s,t);でも同じ。
実は中身ではなく変数の名前などの情報の方を入れ替えるので、中身が長くても一瞬で終わる。

検索系（全体的にB問題レベル）

文字列検索 .find(文字列,開始位置)

s.find("abc",3)と書けば、sの中で3文字目以降に初めて"abc"という並びがある場所を検索する。
返り値は「該当場所の先頭が何文字目か」で、存在しなかった場合はsize_t型の最大値（使いにくいので、一度int型に入れて-1として扱わせるとよい）。
s.find("abc")と開始位置を省略した場合は先頭から検索する。

文字列逆順検索 .rfind(文字列,開始位置)

s.rfind("abc",3)と書けば、sの中で3文字目以前に最後に"abc"という並びがある場所を検索する。
返り値は「該当場所の先頭が何文字目か」で、存在しなかった場合はsize_t型の最大値。
s.rfind("abc")と開始位置を省略した場合は末尾から検索する。

先頭一致判定 .starts_with(文字または文字列)

s.starts_with("abc")と書くと、sが"abc"で始まるか判定し、bool型で返してくれる。

末尾一致判定 .ends_with(文字または文字列)

s.ends_with("abc")と書くと、sが"abc"で始まるか判定し、bool型で返してくれる。

中間一致判定 .contains(文字または文字列)

s.contains("abc")と書くと、sが"abc"を含むか判定し、bool型で返してくれる。

よく使う処理

中身を逆順に並べなおす

reverse(s.begin(),s.end());

文字列が逆順の方が都合がいい場合などに。

回文判定

逆順にしても元と同じ、をそのとおりにやればいい。
元の文字列を残す必要があるので、コピーしてから逆順にすること。

string t = s;
reverse(t.begin(),t.end());
if (s==t) {
  // 回文だった場合のコード
}

中身をアルファベット順に並べる

sort(s.begin(),s.end());

文字の並び順はもはやどうでも壊れてもいいので、中の文字を全部アルファベット順に並べてほしい場合に。

ranges::sort(s);

という書き方もある。

sort(s.rbegin(),s.rend());

なら、逆順に並ぶ。

アナグラム判定

sとtがアナグラムになっているか、つまり文字の順番を入れ替えて一致させられるかを判定したい場合。
sとtを両方「中身をアルファベット順に並べる」をし、結果が一致するか見ればよい。

sort(s.begin(),s.end());
sort(t.begin(),t.end());
if (s==t) {
  // アナグラムだった場合のコード
}

sやtの中身が壊れたら困る場合は、事前に文字列をコピーし、そっちを判定に使うこと。

string str1 = s;
string str2 = t;
sort(str1.begin(),str1.end());
sort(str2.begin(),str2.end());
if (str1==str2) {
  // アナグラムだった場合のコード
}

1文字ずつ何か処理する

.at(i)で1文字ずつ見ていく。
長さnが与えられている場合

for (int i=0; i<n; i++) {
  // 中身の文字s.at(i)に対してしたいことを書く
}

長さnが与えられていない場合
（一度.size()で長さを取得してから上のやつを用いてもよい）

for (size_t i=0; i<s.size(); i++) {
  // 中身の文字s.at(i)に対してしたいことを書く
}

1文字ずつ何か処理する、その2（B問題レベル）

範囲for文（未作成）で1文字ずつ取り出すことができる。

for (char c : s) {
  // 中身の文字cに対してしたいことを書く
}

中身の書き換えまでしたい場合はchar&として参照渡し（未作成）をする。

文字ごとの出現回数を全種カウント

文字列を見て、'a'が何回、'b'が何回、'c'が何回、（中略）、'z'が何回、とカウントする方法。

vector<int> counters(26);
for (int i=0; i<n; i++) {
  counters.at(s.at(i)-'a')++;
}

countersの、.at(0)に'a'の個数、.at(1)に'b'の個数、（中略）、.at(25)に'z'の個数、が入る。
コピペする場合、ループの終了条件のnの部分をsの文字数に書き換えること。
あるいは、範囲for文（未作成）が使いこなせるのであれば、下のやつの方が使いやすい。

vector<int> counters(26);
for (char c : s) {
  counters.at(c-'a')++;
}

指定文字で分割（B問題レベル）

例えば"abc,de,fghi"という文字列を','で分割してvector（未作成）<string>に変更したい場合。

vector<string> parts(1,"");
for (char c : s) {
  if (c==',') parts.emplace_back("");
  else parts.back() += c;
}

if文の中を変更すれば、他の文字での分割もできる。

数値化（B問題レベル）

文字列型をint型にしたい場合、

stoi(s)

とするが、int型に収まるかどうかを確認すること。
同様にstoll()でlong long型に、stod()でdouble型にできる。

逆に、int型の数であるaを文字列型に変換したい場合、

to_string(a)

とすればいい。
to_string()（未作成）とstoi()（未作成）も参照。

注意点

処理速度に注意。（C問題レベル）

長さnの文字列は、それ自体1つの変数のように扱えるが、実際の中身は長さがnのvector（未作成）<char>に近い。
つまり、中身を1文字ずつ見ていく系の処理や、先頭や途中の文字が増減する処理は、O(n)かかる。
コードの見た目で処理時間を見積もるとわりと痛い目を見るので注意。

関連アルゴリズム