概要

長さ \(N\) のビット列 \(S\) から、同じ長さの連続部分文字列のペアで、ハミング距離がちょうど \(1\) であるものの個数を数える問題です。

考察

素朴なアプローチとその限界

すべてのペア \(((l_1, r_1), (l_2, r_2))\) を全探索すると、長さ \(L\) を固定しても開始位置の組が \(O(N^2)\) 通り、さらに長さも \(O(N)\) 通りあるため、全体で \(O(N^3)\) 以上の計算量となり、\(N = 5000\) では間に合いません。

重要な気づき：「シフト量」で整理する

2つの部分文字列の開始位置の差を シフト量 \(d = l_2 - l_1\)（\(d \geq 1\)）として固定して考えます。すると、同じ長さ \(L\) のペアは次のように表せます：

• 1つ目の部分文字列：\(S[k], S[k+1], \ldots, S[k+L-1]\)
• 2つ目の部分文字列：\(S[k+d], S[k+d+1], \ldots, S[k+d+L-1]\)

各位置 \(k\) で \(S[k]\) と \(S[k+d]\) が一致するかどうかを調べ、不一致位置（ミスマッチ位置） を列挙します。ペアのハミング距離が \(1\) であるとは、区間 \([k, k+L-1]\) の中にミスマッチ位置がちょうど \(1\) つだけ含まれることに他なりません。

ミスマッチ位置ごとに数え上げる

シフト量 \(d\) を固定したとき、ミスマッチ位置を \(p_0 < p_1 < \cdots < p_{m-1}\) とします。

各ミスマッチ位置 \(p_j\) について、「\(p_j\) だけを含みそれ以外のミスマッチ位置を含まない区間」の個数を数えます。

区間 \([k, k+L-1]\) が \(p_j\) のみを含むためには： - 左端の制約：\(k\) は \(p_j\) 以下、かつ前のミスマッチ \(p_{j-1}\) を含まないため \(k \geq p_{j-1} + 1\)（\(j = 0\) なら \(k \geq 0\)） - 右端の制約：\(k+L-1\) は \(p_j\) 以上、かつ次のミスマッチ \(p_{j+1}\) を含まないため \(k+L-1 \leq p_{j+1} - 1\)（\(j = m-1\) なら \(k+L-1 \leq N-1-d\)）

左端の選び方が \((p_j - \text{left\_bound} + 1)\) 通り、右端の選び方が \((\text{right\_bound} - p_j + 1)\) 通りなので、その積が \(p_j\) に対応するペア数です。

具体例：\(S = \) 0110, \(d = 2\) のとき、\(S[0]\) vs \(S[2]\)（0 vs 1：不一致）、\(S[1]\) vs \(S[3]\)（1 vs 0：不一致）。ミスマッチ位置は \(\{0, 1\}\)。\(p_0 = 0\) について、左端 \(= 0\)、右端 \(= 0\)（\(p_1 - 1 = 0\)）なので \(1 \times 1 = 1\) 通り。\(p_1 = 1\) について、左端 \(= 1\)（\(p_0 + 1 = 1\)）、右端 \(= 1\) なので \(1 \times 1 = 1\) 通り。合計 \(2\) ペア。

アルゴリズム

1. シフト量 \(d\) を \(1\) から \(N-1\) まで順に試す。
2. 各 \(d\) について、\(k = 0, 1, \ldots, N-1-d\) の範囲で \(S[k] \neq S[k+d]\) となるミスマッチ位置を列挙する。
3. 各ミスマッチ位置 \(p_j\) について、隣接するミスマッチ位置（または境界）から左右の選択肢数を計算し、その積を答えに加算する。

計算量

• 時間計算量: \(O(N^2)\) — シフト量 \(d\) が \(O(N)\) 通り、各 \(d\) に対して \(O(N)\) の処理
• 空間計算量: \(O(N)\) — ミスマッチ位置のリスト

実装のポイント

• ペアは順序なしで数えるため、シフト量 \(d\) を正の値のみ（\(d \geq 1\)）で回せば自然に重複なく数え上げられます。

• ミスマッチ位置が \(0\) 個のシフト量はスキップでき、無駄な計算を省けます。

• 各ミスマッチ位置の「左の境界」は前のミスマッチ位置 \(+1\)、「右の境界」は次のミスマッチ位置 \(-1\) で簡潔に表現できます。境界（先頭・末尾）の処理に注意しましょう。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    S = input_data[1].decode()
    
    # For each pair of starting positions (i, j) with i < j,
    # we need to count pairs of substrings of equal length that differ in exactly 1 position.
    #
    # For a fixed shift d = j - i (where d >= 1), consider comparing S[i:] and S[i+d:].
    # Let's define for each d, the match array: match[k] = 1 if S[k] == S[k+d], else 0,
    # for k = 0, 1, ..., N-1-d.
    #
    # For two substrings (l1, r1) = (k+1, k+L) and (l2, r2) = (k+d+1, k+d+L),
    # they have Hamming distance 1 over length L iff exactly one of match[k], match[k+1], ..., match[k+L-1] is 0.
    #
    # For a fixed d, let the positions where match[k] = 0 be at indices p_0, p_1, ..., p_{m-1}.
    # A substring pair of length L starting at position k (in the first string) has exactly one mismatch
    # iff the window [k, k+L-1] contains exactly one of the p_i.
    #
    # For each consecutive pair of mismatch positions (p_{j}, p_{j+1}), and also boundaries,
    # we can count how many (k, L) windows contain exactly p_j as the only mismatch.
    #
    # Actually, let me think differently. For fixed d, let mismatch positions be p_0 < p_1 < ... < p_{m-1}.
    # The valid range for k is [0, N-d-L] and L >= 1, but it's easier to think in terms of intervals.
    #
    # For each mismatch position p_j, the window [k, k+L-1] must contain p_j but not p_{j-1} or p_{j+1}.
    # Let left_bound = p_{j-1} + 1 if j > 0 else 0
    # Let right_bound = p_{j+1} - 1 if j < m-1 else (N - 1 - d)
    # The window must satisfy: k <= p_j and k + L - 1 >= p_j,
    # also k >= left_bound and k + L - 1 <= right_bound.
    # So: left_bound <= k <= p_j and p_j <= k + L - 1 <= right_bound.
    # Let end = k + L - 1, so: k ranges in [left_bound, p_j], end ranges in [p_j, right_bound].
    # Also end >= k, which is guaranteed since end >= p_j >= k.
    # The number of (k, end) pairs = (p_j - left_bound + 1) * (right_bound - p_j + 1).
    # Each (k, end) pair corresponds to a unique (k, L) with L = end - k + 1 >= 1.
    
    total = 0
    
    for d in range(1, N):
        # Compare S[k] vs S[k+d] for k = 0, 1, ..., N-1-d
        length = N - d
        # Collect mismatch positions
        mismatches = []
        for k in range(length):
            if S[k] != S[k + d]:
                mismatches.append(k)
        
        if not mismatches:
            continue
        
        m = len(mismatches)
        max_pos = length - 1  # maximum valid index
        
        for j in range(m):
            left_bound = (mismatches[j - 1] + 1) if j > 0 else 0
            right_bound = (mismatches[j + 1] - 1) if j < m - 1 else max_pos
            
            left_count = mismatches[j] - left_bound + 1
            right_count = right_bound - mismatches[j] + 1
            
            total += left_count * right_count
    
    print(total)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。