String - tanakakenji/Rinko GitHub Wiki
文字列は文字の配列です。配列に適用される多くのヒントは文字列にも適用されます。このページを読む前に、配列に関するページを読むことをお勧めします。
文字列の検索に使用される一般的なデータ構造：
文字列は文字の配列なので、基本的な文字列操作の時間複雑度は配列操作のそれと密接に関連しています。
| 操作 | ビッグO表記 |
|---|---|
| アクセス | O(1) |
| 検索 | O(n) |
| 挿入 | O(n) |
| 削除 | O(n) |
ここでは、もう一方の文字列の長さをmとします。
| 操作 | ビッグO表記 | 注釈 |
|---|---|---|
| 部分文字列の検索 | O(n・m) | これは最も単純な場合。KMPアルゴリズムなど、より効率的な文字列検索アルゴリズムがあります |
| 文字列の連結 | O(n + m) | |
| スライス | O(m) | |
| 分割（トークンによる） | O(n + m) | |
| ストリップ（先頭と末尾の空白を削除） | O(n) |
入力文字セットと大文字小文字の区別について尋ねましょう。通常、文字はaからzの小文字のラテン文字に限定されています。
文字列処理アルゴリズムやデータ構造を設計・実装する際、様々な入力ケースを考慮することが重要です。ここで挙げられているコーナーケースは、多くの文字列処理タスクで特別な注意が必要な状況を示しています。
空の文字列（長さが0の文字列）は、多くのアルゴリズムで特別な扱いが必要になることがあります。
- 検索アルゴリズム: 空の文字列を検索パターンとして使用した場合、全ての位置にマッチする可能性があります。
- 部分文字列操作: 空の文字列から部分文字列を抽出しようとすると、範囲外アクセスのエラーが発生する可能性があります。
std::string text = "";
if (text.empty()) {
std::cout << "文字列が空です" << std::endl;
}非常に短い文字列は、一部のアルゴリズムで特別な処理が必要になることがあります。
- パターンマッチング: KMPアルゴリズムなどで、パターンが1文字や2文字の場合、前処理が不要になる可能性があります。
- 文字列の回転: 1文字の文字列を回転させても変化がありません。
std::string s = "a";
if (s.length() <= 2) {
std::cout << "文字列が1文字または2文字です" << std::endl;
}同じ文字が連続して繰り返される文字列は、一部のアルゴリズムで最悪のケースを引き起こす可能性があります。
- 単純な文字列マッチング: "aaaaa"のような文字列で多数の比較が発生する可能性があります。
- 圧縮アルゴリズム: ランレングス符号化などで特に効果的に圧縮できる可能性があります。
std::string repeated = "aaaaaa";
char first = repeated[0];
bool allSame = std::all_of(repeated.begin(), repeated.end(),
[first](char c) { return c == first; });
if (allSame) {
std::cout << "全ての文字が同じです" << std::endl;
}全ての文字が異なる文字列は、一部のアルゴリズムで特別な振る舞いをする可能性があります。
- ハッシュベースのアルゴリズム: コリジョンが発生しにくくなる可能性があります。
- 圧縮アルゴリズム: 効果的な圧縮が難しくなる可能性があります。
std::string unique = "abcdefg";
std::set<char> charSet(unique.begin(), unique.end());
if (charSet.size() == unique.length()) {
std::cout << "全ての文字が異なります" << std::endl;
}文字列内の文字の頻度をカウントする必要がある場合が多くあります。最も一般的な方法は、ハッシュテーブル/マップを使用することです。
注意：ラテン文字の文字列のカウンターに必要なスペースの複雑さはO(n)ではなくO(1)です。これは、上限が文字の範囲（通常26の固定定数）だからです。
ユニークな文字で構成される文字列の文字をカウントするための巧妙な方法として、26ビットのビットマスクを使用して、どの小文字のラテン文字が文字列内にあるかを示すことができます。
2つの文字列に共通の文字があるかどうかを判断するには、2つのビットマスクに対して「&」演算を実行します。結果が0でない場合、2つの文字列には共通の文字があります。
アナグラムは単語の並べ替えや言葉遊びです。元の単語やフレーズのすべての文字を1回ずつ使用して、新しい単語やフレーズを作成することです。
2つの文字列がアナグラムであるかどうかを判断する方法：
回文は、前から読んでも後ろから読んでも同じ語句になる単語、フレーズ、数字、またはその他の文字の並びです。
回文の数を数える問題では、中央から外側に向かって移動する2つのポインタを使用するのが一般的なテクニックです。回文は偶数または奇数の長さである可能性があることに注意してください。
これらの例は、部分文字列の場合を示しています。部分列の場合は、重複する部分問題があるため、動的プログラミングを使用する必要があります。