N - 周期文字列の作成 / Creating a Periodic String 解説 by admin
gpt-5.5-high概要
削除操作は「先頭から \(x\) 文字、末尾から \(M-x\) 文字を残す」と言い換えられます。
各結果文字列が周期文字列かどうかを、Z-algorithm とメビウス関数を用いて効率よく数えます。
考察
削除後の文字列の長さを \(M\) とします。削除操作では少なくとも \(1\) 文字削除するので、\(0 \leq M \leq N-1\) です。
長さ \(M\) の文字列を作るには、
- 先頭から \(x\) 文字残す
- 末尾から \(M-x\) 文字残す
と考えることができます。
つまり削除後の文字列 \(T\) は
\[ T = S[0:x] + S[N-(M-x):N] \]
です。
ここで \(0 \leq x \leq M\) です。
この \((M, x)\) は削除区間の選び方と一対一に対応します。
周期文字列とは、ある \(d < M\) について
\[ T_i = T_{i+d} \]
がすべての \(0 \leq i < M-d\) で成り立ち、さらに \(d\) が \(M\) を割り切るようなものです。
このとき \(T\) は長さ \(d\) のブロックを \(k = M/d\) 回繰り返した文字列です。
単純にすべての削除操作を試すと \(O(N^2)\) 個あり、さらに周期判定を行うと間に合いません。
そこで、固定した周期長 \(d\) と繰り返し回数 \(k\) に対して、条件を満たす \(x\) の個数をまとめて数えます。
長さ \(M = dk\) の文字列 \(T\) が周期長 \(d\) を持つ条件を考えます。
比較すべき位置は
\[ T_i = T_{i+d} \]
で、範囲は \(0 \leq i < M-d\) です。
ここで
\[ C = M-d \]
とおきます。
比較は次の3種類に分かれます。
1. 両方が先頭から残した部分にある場合
これは \(S\) の先頭部分が周期 \(d\) を持つ必要があります。
Z-algorithm により、
\[ A[d] = d + \operatorname{LCP}(S[0:], S[d:]) \]
を求めると、先頭から長さ \(A[d]\) までは周期 \(d\) を持ちます。
したがって必要条件は
\[ x \leq A[d] \]
です。
2. 両方が末尾から残した部分にある場合
同様に、末尾部分が周期 \(d\) を持つ必要があります。
これは反転文字列に対して Z-algorithm を使えば求められます。
末尾から長さ \(B[d]\) までは周期 \(d\) を持つとして、
\[ M-x \leq B[d] \]
が必要です。
つまり
\[ x \geq M - B[d] \]
です。
よって、まず \(x\) は次の範囲に入る必要があります。
\[ \max(0, M-B[d]) \leq x \leq \min(M, A[d]) \]
3. 比較が「先頭部分」と「末尾部分」をまたぐ場合
この場合、周期 \(d\) が成り立つには、先頭の長さ \(d\) の部分と、末尾の長さ \(d\) の部分の対応する文字が一致している必要があります。
つまり、各 \(0 \leq t < d\) について
\[ S[t] = S[N-d+t] \]
を見ることになります。
ただし、分割位置 \(x\) によって必要な範囲が変わります。
- \(x\) が左端に近い場合：先頭側の一部だけ見ればよい
- \(x\) が中央付近の場合：長さ \(d\) 全体が一致している必要がある
- \(x\) が右端に近い場合：末尾側の一部だけ見ればよい
そこで、
firstBad[d]：\(S[0:d]\) と \(S[N-d:N]\) を左から見た最初の不一致位置lastBad[d]：右から見た最後の不一致位置
を求めます。
もし \(S[0:d] = S[N-d:N]\) なら、またぐ比較は常に問題ありません。
そうでない場合、またぐ比較が成立するのは次のどちらかです。
\[ x \leq \text{firstBad}[d] \]
または
\[ x \geq C + \text{lastBad}[d] + 1 \]
です。
したがって、先ほど求めた \(x\) の候補範囲との共通部分の長さを数えれば、固定した \((d, M)\) に対する個数が分かります。
重複カウントを避ける
ある文字列は複数の周期長を持つことがあります。
例えば aaaa は
- 長さ \(1\) のブロックを \(4\) 回
- 長さ \(2\) のブロックを \(2\) 回
と見ることができます。
そのため、単純に周期長ごとに数えると重複します。
ここでメビウス関数 \(\mu\) を使います。
長さ \(M\) の文字列が、最小周期によって \(q\) 回の繰り返しになっているとします。
この文字列は、\(k\) が \(q\) の約数であるとき、\(k\) 回繰り返しの文字列としても見なせます。
そこで、繰り返し回数 \(k\) に対して重み
\[ -\mu(k) \]
を掛けて足し合わせます。
周期文字列でない場合は \(q=1\) なので寄与は \(0\)、周期文字列の場合は
\[ \sum_{\substack{k \mid q \\ k \geq 2}} -\mu(k) = 1 \]
となります。
これにより、周期文字列をちょうど1回だけ数えられます。
アルゴリズム
- 文字列 \(S\) に対して Z-algorithm を行う。
- 反転文字列にも Z-algorithm を行う。
- 各 \(d\) について以下を前計算する。
A[d]：先頭から周期 \(d\) が続く最大長B[d]：末尾から周期 \(d\) が続く最大長firstBad[d]：先頭 \(d\) 文字と末尾 \(d\) 文字の左から最初の不一致位置lastBad[d]：先頭 \(d\) 文字と末尾 \(d\) 文字の右から最後の不一致位置
- メビウス関数 \(\mu\) を線形篩で求める。
- 繰り返し回数 \(k \geq 2\) を全探索する。
- 係数は
coeff = -mu[k] - \(M = dk < N\) となる \(d\) を全探索する。
- 固定した \(d, M\) について、周期 \(d\) を持つ削除操作数 \(F\) を求める。
- 答えに
coeff * Fを加える。
- 係数は
- 最後に、操作1、つまり削除しない場合を別途判定する。
- \(S\) 自体が周期文字列なら答えに \(1\) を加える。
- これは prefix function により最小周期を求めて判定する。
計算量
- 時間計算量: \(O(N \log N)\)
- 空間計算量: \(O(N)\)
\(k, d\) の二重ループは
\[ \sum_{k=2}^{N} \frac{N}{k} = O(N \log N) \]
です。
Z-algorithm、prefix function、メビウス関数の前計算はいずれも \(O(N)\) です。
実装のポイント
削除操作は \((M, x)\) で考えると扱いやすいです。
- \(M\) は削除後の長さ
- \(x\) は先頭から残す文字数
削除操作では \(M < N\) なので、メインのループでは \(dk \leq N-1\) だけを扱います。
削除しない操作は別に1通りだけ存在するため、最後に \(S\) 自体が周期文字列か判定します。
空文字列と長さ \(1\) の文字列は周期文字列ではありませんが、ループでは \(k \geq 2, d \geq 1\) なので自然に長さ \(2\) 以上だけが対象になります。
ソースコード
#include <bits/stdc++.h>
using namespace std;
vector<int> z_function(const string& s) {
int n = (int)s.size();
vector<int> z(n);
if (n == 0) return z;
z[0] = n;
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i <= r) z[i] = min(r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
vector<int> prefix_function(const string& s) {
int n = (int)s.size();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
}
vector<int> mobius(int n) {
vector<int> mu(n + 1), primes;
vector<bool> comp(n + 1);
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!comp[i]) {
primes.push_back(i);
mu[i] = -1;
}
for (int p : primes) {
if ((long long)i * p > n) break;
comp[i * p] = true;
if (i % p == 0) {
mu[i * p] = 0;
break;
} else {
mu[i * p] = -mu[i];
}
}
}
return mu;
}
long long intersect_count(int l1, int r1, int l2, int r2) {
int l = max(l1, l2);
int r = min(r1, r2);
if (l > r) return 0;
return (long long)r - l + 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
string S;
cin >> N >> S;
vector<int> z = z_function(S);
string R = S;
reverse(R.begin(), R.end());
vector<int> zr = z_function(R);
vector<int> A(N + 1), B(N + 1), firstBad(N + 1), lastBad(N + 1);
for (int d = 1; d < N; d++) {
A[d] = min(N, d + z[d]);
B[d] = min(N, d + zr[d]);
int fb = z[N - d];
if (fb > d) fb = d;
firstBad[d] = fb;
int eb = zr[N - d];
if (eb > d) eb = d;
if (eb >= d) lastBad[d] = -1;
else lastBad[d] = d - 1 - eb;
}
vector<int> mu = mobius(N);
long long ans = 0;
for (int k = 2; k <= N - 1; k++) {
int coeff = -mu[k];
if (coeff == 0) continue;
int maxd = (N - 1) / k;
for (int d = 1; d <= maxd; d++) {
int M = d * k;
int C = M - d;
int lo = max(0, M - B[d]);
int hi = min(M, A[d]);
if (lo > hi) continue;
long long F = 0;
if (firstBad[d] == d) {
F = (long long)hi - lo + 1;
} else {
F += intersect_count(lo, hi, 0, firstBad[d]);
F += intersect_count(lo, hi, C + lastBad[d] + 1, M);
}
ans += (long long)coeff * F;
}
}
if (N >= 2) {
vector<int> pi = prefix_function(S);
int p = N - pi[N - 1];
if (p < N && N % p == 0) ans++;
}
cout << ans << '\n';
return 0;
}
この解説は gpt-5.5-high によって生成されました。
投稿日時:
最終更新: