概要

長さが等しい 2 つの部分文字列のペアで、対応する文字が異なる位置（ハミング距離）が ちょうど 1 になるものを、重複なく数え上げます。
鍵は「開始位置の差 \(d\) を固定すると、比較は 1 本の対角線（オフセット）上の問題になる」という観察です。

考察

素朴解が厳しい理由

部分文字列は \(O(N^2)\) 個あります。これらのペアは \(O(N^4)\) 個になり、さらにハミング距離計算に長さ分かかると到底間に合いません。

重要な気づき：開始位置差 \(d\) で整理する

2 つの部分文字列を - 1つ目：\(S[l..r]\) - 2つ目：\(S[l+d..r+d]\)（開始位置が \(d\) だけ後ろ）

のように 開始位置差 \(d>0\) で揃えると、比較する文字は常に - \(S[i]\) と \(S[i+d]\)

の形になります。これは文字列上で「距離 \(d\) だけ離れた文字同士を並べて比較する」ことと同じです。

このとき、\(i=0,1,\dots,N-d-1\) について - diff[i] = (S[i] != S[i+d])（違えば 1、同じなら 0）

という配列（長さ \(M=N-d\)）を考えると、

開始位置 \(i\)、長さ \(L\) の 2 部分文字列ペアのハミング距離
＝ diff[i] から diff[i+L-1] の 1 の個数

になります。
つまり「ハミング距離がちょうど 1」⇔「diff のある区間に 1 がちょうど 1 個」です。

diff の区間で「1 がちょうど 1 個」の数え方

diff で 1 が立っている位置を昇順に $\(p_1 < p_2 < \dots < p_k\)$ とします（0-indexed）。

ある \(p_j\) を「区間内で唯一の 1」にする区間の取り方は：

• 左端は 前の 1 の次 から \(p_j\) まで選べる
  個数：\(p_j - p_{j-1}\)（ただし \(p_0=-1\) とみなす）
• 右端は \(p_j\) から 次の 1 の前 まで選べる
  個数：\(p_{j+1} - p_j\)（ただし \(p_{k+1}=M\) とみなす）

よって、\(p_j\) が唯一の 1 になる区間数は $\( (p_j - p_{j-1}) (p_{j+1} - p_j) \)\( これを全ての 1 について足せば、その \)d$ に対する答えになります。

また、順序なしペアですが、任意のペアは「開始位置が小さい方を先」と決めると \(d=l_2-l_1>0\) が一意なので、\(d=1..N-1\) だけ数えれば 重複なく 数えられます。

アルゴリズム

1. 答え ans=0。
2. \(d=1,2,\dots,N-1\) について繰り返す：
   1. \(M=N-d\) とする。
   2. pos に「S[i] != S[i+d] となる位置 \(i\)」を全て格納する（= diff の 1 の位置）。
   3. 末尾番兵として pos.append(M) を追加する（次の 1 が無い場合を一括処理するため）。
   4. prev=-1 として、pos の各要素 \(p\)（最後の番兵は除く）について
      • ans += (p - prev) * (next_p - p)
      • prev = p
3. ans を出力。

（コードでは s を bytes にして s[i] != s[i+d] を高速に比較しています。）

計算量

• 時間計算量: \(O(N^2)\)
  各 \(d\) で \(O(N-d)\) 走査し、総和が \(\sum_{d=1}^{N-1}(N-d)=O(N^2)\)
• 空間計算量: \(O(N)\)
  pos が最大で \(O(N)\) 要素

実装のポイント

• pos の末尾に番兵 M を入れると、「最後の 1 の右側の伸び」を特別扱いせずに同じ式で処理できます。

• prev=-1 とすることで、「最初の 1 の左側の伸び」も同様に扱えます。

• 答えは最大で非常に大きくなり得ますが、Python の int は多倍長なのでそのままで問題ありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    s = input().strip().encode()

    ans = 0
    n = N
    for d in range(1, n):
        M = n - d
        pos = []
        append = pos.append
        sd = d
        for i in range(M):
            if s[i] != s[i + sd]:
                append(i)

        if pos:
            pos.append(M)  # sentinel as "second mismatch" for the last one
            prev = -1
            for idx in range(len(pos) - 1):
                p = pos[idx]
                ans += (p - prev) * (pos[idx + 1] - p)
                prev = p

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。