E - 円環文字列の検索 / Searching in a Circular String Editorial by admin Editorial for printing
gemini-3.5-flash-thinking概要
この問題は、円環状に並んだ文字列 \(S\) の中から、パターン文字列 \(T\) と一致する連続した部分文字列の開始位置が何箇所あるかを求める問題です。
円環上の文字列を扱うために、文字列 \(S\) を適切に引き伸ばした新しい文字列 \(S'\) を作成し、文字列の高速なパターンマッチングアルゴリズムである Z-algorithm を適用することで、高速に解くことができます。
考察
1. 円環状の文字列をどう扱うか？
円環状の文字列 \(S\)（長さ \(N\)）において、各開始位置 \(i\)（\(0 \leq i < N\)）から始まる長さ \(M\) の文字列 \(R_i\) を考えます。 例えば、\(S = \text{"abc"}\)（\(N=3\)）、\(T = \text{"cab"}\)（\(M=3\)）のとき、開始位置 \(i=2\) から始まる \(3\) 文字は、末尾から先頭に戻って \(\text{"cab"}\) となります。
このように「末尾の後に先頭が続く」という円環の性質を扱うための典型的なテクニックは、文字列を繰り返して引き伸ばすことです。 開始位置は \(0\) から \(N-1\) までの \(N\) 通りあり、それぞれから最大 \(M\) 文字を読み取るため、インデックスとしては最大で \((N-1) + (M-1) = N + M - 2\) までアクセスすることになります。
したがって、元の文字列 \(S\) を \(i \bmod N\) の位置の文字で埋めながら、長さ \(N + M - 1\) まで引き伸ばした文字列 \(S'\) を作成すれば、円環上のすべての開始位置からの長さ \(M\) の文字列を、直線上の部分文字列として表現できます。
\(S = \text{"abc"}\) (\(N=3\)), \(T = \text{"cab"}\) (\(M=3\)) の場合： \(S'\) は長さ \(3 + 3 - 1 = 5\) の文字列となり、 \(S' = \text{"abcab"}\) となります。 - \(i = 0\) からの \(3\) 文字：\(S'[0..2] = \text{"abc"}\) - \(i = 1\) からの \(3\) 文字：\(S'[1..3] = \text{"bca"}\) - \(i = 2\) からの \(3\) 文字：\(S'[2..4] = \text{"cab"}\)
このように、円環の問題を「文字列 \(S'\) の中から、パターン \(T\) と一致する開始位置を探す」という通常の文字列探索問題に帰着させることができました。
2. 素朴なアプローチとその限界
各開始位置 \(i\)（\(0 \leq i < N\)）について、直線上になった \(S'\) の部分文字列 \(S'[i \dots i+M-1]\) が \(T\) と一致するかを愚直に比較すると、1回の比較に最悪 \(O(M)\) かかります。 全体で \(O(NM)\) の計算量となり、制約である \(N, M \leq 5 \times 10^5\) では、最悪の場合 \(2.5 \times 10^{11}\) 回程度の計算が必要になり、実行時間制限（TLE）に間に合いません。
3. Z-algorithm による高速化
文字列のパターンマッチングを高速に行うために、Z-algorithm を使用します。 Z-algorithm は、ある文字列 \(U\) に対し、各位置 \(k\) から始まる部分文字列が、文字列 \(U\) 全体の接頭辞と最大で何文字一致しているか（最長共通接頭辞の長さ）を、すべての \(k\) について \(O(|U|)\) 時間で計算するアルゴリズムです。
これを利用するために、以下のような新しい文字列 \(U\) を構築します。 $\(U = T + \text{"\#"} + S'\)\( ここで、`"#"` は \)S\( や \)T$ に含まれない特殊な文字（区切り文字）です。
この文字列 \(U\) に対して Z-algorithm を適用すると、配列 \(Z\) が得られます。 \(U\) の中で \(S'\) が始まるのはインデックス \(M+1\) 以降です。 各 \(i\)（\(0 \leq i < N\)）について、元の \(S\) の開始位置 \(i\) に対応する \(U\) のインデックスは \(M + 1 + i\) となります。 もし \(Z[M + 1 + i] \geq M\) であれば、その位置から始まる部分文字列は \(T\) と \(M\) 文字以上一致している（＝ \(T\) と完全に一致している）と判定できます。
アルゴリズム
具体例として、\(S = \text{"abc"}\) (\(N=3\)), \(T = \text{"cab"}\) (\(M=3\)) の場合の流れを追ってみましょう。
引き伸ばした文字列 \(S'\) の作成 \(S'\) の長さを \(N + M - 1 = 5\) とし、順に \(S[i \bmod N]\) を追加します。 \(S' = \text{"abcab"}\) となります。
探索用文字列 \(U\) の作成 \(T\)、区切り文字
"#"、 \(S'\) を連結します。 \(U = \text{"cab\#abcab"}\) （長さ \(9\)）となります。Z-algorithm の適用 文字列 \(U\) に対する Z-algorithm の結果（配列 \(Z\)）は以下のようになります。
| インデックス \(k\) | \(U[k]\) | \(U[k:]\) | 接頭辞 \(U = \text{"cab..."}\) との一致長 \(Z[k]\) |
| :—: | :—: | :— | :—: |
| 0 | ‘c’ | "cab#abcab" | 9 |
| 1 | ‘a’ | "ab#abcab" | 0 |
| 2 | ‘b’ | "b#abcab" | 0 |
| 3 | ‘#’ | "#abcab" | 0 |
| 4 (\(i=0\)) | ‘a’ | "abcab" | 0 |
| 5 (\(i=1\)) | ‘b’ | "bcab" | 0 |
| 6 (\(i=2\)) | ‘c’ | "cab" | 3 （\(\text{"cab"}\) と一致） |
| 7 | ‘a’ | "ab" | 0 |
| 8 | ‘b’ | "b" | 0 |
- 判定とカウント \(i = 0, 1, 2\) のうち、\(Z[M + 1 + i] \geq M\) となるのは \(i = 2\) のとき（\(Z[6] = 3 \geq 3\)）のみです。 よって、一致する開始位置の個数は \(1\) と求まります。
計算量
時間計算量: \(O(N + M)\)
- 文字列 \(S'\) の構築に \(O(N + M)\) 時間かかります。
- 構築した文字列 \(U\) の長さは \(N + 2M\) です。Z-algorithm は線形時間で動作するため、実行時間は \(O(|U|) = O(N + M)\) です。
- 答えの判定ループは \(N\) 回であり、\(O(N)\) です。
- 全体として \(O(N + M)\) となり、制約下で非常に高速に（0.1秒未満で）動作します。
空間計算量: \(O(N + M)\)
- 文字列 \(S', U\) や、Z-algorithm の結果を格納する配列 \(Z\) を保持するために、長さ \(O(N + M)\) のメモリを使用します。
実装のポイント
\(M > N\) の場合への対応 \(M\) が \(N\) より大きい場合、円環を \(1\) 周以上することになります。 文字列 \(S'\) を構築する際に、
S[i % N]と剰余演算（%）を用いることで、自動的に何周でもループして文字を補完することができます。区切り文字の重要性 \(T\) と \(S'\) の間に挿入する文字（今回は
"#"）は、入力に含まれない文字である必要があります。 これがないと、マッチングが \(T\) の境界を越えて \(S'\) 側に突き抜けてしまい、正しく判定できなくなる原因になります。メモリの事前確保（reserve） C++ において
std::stringの結合を繰り返すと、メモリの再確保が何度も発生してボトルネックになることがあります。S_prime.reserve(N + M)を呼んであらかじめメモリ領域を確保しておくことで、定数倍の高速化を図っています。ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <atcoder/string>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string S, T;
if (!(cin >> S >> T)) return 0;
int N = S.length();
int M = T.length();
string S_prime = "";
S_prime.reserve(N + M);
for (int i = 0; i < N + M - 1; ++i) {
S_prime += S[i % N];
}
string U = T + "#" + S_prime;
vector<int> z = atcoder::z_algorithm(U);
int ans = 0;
for (int i = 0; i < N; ++i) {
if (z[M + 1 + i] >= M) {
ans++;
}
}
cout << ans << "\n";
return 0;
}
この解説は gemini-3.5-flash-thinking によって生成されました。
posted:
last update: