概要

文字列のすべてのボーダー（接頭辞かつ接尾辞である部分文字列）の長さを求め、ボーダーが0個なら0、1個ならその長さ、2個以上なら長さの隣接差のGCDを出力する問題です。KMP法の失敗関数（failure function）を用いて効率的にボーダーを列挙します。

考察

ボーダーとは何か

文字列 \(S\) のボーダーとは、\(S\) の「接頭辞であると同時に接尾辞でもある」真部分文字列です。例えば abcab では、先頭2文字 ab と末尾2文字 ab が一致するので、ab はボーダーです。

素朴なアプローチの問題点

長さ \(1\) から \(|S|-1\) まですべて試して接頭辞と接尾辞が一致するか確認すると、各文字列について \(O(|S|^2)\) かかり、全体で最大 \(10^{12}\) 程度の計算になりTLEします。

重要な気づき：KMP の失敗関数

KMP法で用いる失敗関数 \(\text{fail}[i]\) は、「\(S[0..i]\)（長さ \(i+1\) の接頭辞）の最長のボーダーの長さ」を表します。

特に \(\text{fail}[n-1]\)（\(n = |S|\)）は、文字列 \(S\) 全体の最長ボーダーの長さです。

さらに、\(S\) のすべてのボーダーは、失敗関数のチェーンをたどることで列挙できます。具体的には： - \(v_1 = \text{fail}[n-1]\) が最長ボーダーの長さ - \(v_2 = \text{fail}[v_1 - 1]\) が2番目に長いボーダーの長さ - \(v_3 = \text{fail}[v_2 - 1]\) が3番目に長いボーダーの長さ - …（\(v = 0\) になるまで繰り返す）

これは、長さ \(v_1\) のボーダー自身のボーダーが、元の文字列のボーダーでもあるという性質に基づきます。

例：abababab

• \(\text{fail} = [0, 0, 1, 2, 3, 4, 5, 6]\)
• \(\text{fail}[7] = 6\) → ボーダー長 \(6\)（ababab）
• \(\text{fail}[5] = 4\) → ボーダー長 \(4\)（abab）
• \(\text{fail}[3] = 2\) → ボーダー長 \(2\)（ab）
• \(\text{fail}[1] = 0\) → 終了

ボーダーの長さは昇順で \(2, 4, 6\)。隣接差は \(2, 2\) でGCDは \(2\)。

アルゴリズム

1. 各文字列 \(S\) に対してKMP法の失敗関数を \(O(|S|)\) で計算する。
2. \(\text{fail}[n-1]\) から失敗関数のチェーンをたどり、すべてのボーダーの長さを集める。
3. ボーダーの個数 \(k\) に応じて：
   • \(k = 0\)：\(0\) を出力
   • \(k = 1\)：その長さを出力
   • \(k \geq 2\)：昇順に並べて隣接差のGCDを計算し出力

計算量

• 時間計算量: \(O(\sum |S_i|)\)
  • 失敗関数の構築は各文字列に対して \(O(|S_i|)\)
  • ボーダーの列挙（チェーンをたどる回数）も合計 \(O(|S_i|)\) 以下
• 空間計算量: \(O(\max |S_i|)\)（失敗関数の配列）

実装のポイント

• 失敗関数のチェーンをたどると、ボーダーは長い方から短い方へ得られるため、GCD計算前にreverseして昇順にしています（ただしGCDの計算自体は差を取るだけなので、降順のまま隣接差を取っても絶対値が同じなので実はどちらでも構いません）。

• 入力が大量になる可能性があるため、sys.stdin.buffer.read() でまとめて読み込み、出力も '\n'.join() でまとめて書き出すことで高速化しています。

• 長さ1以下の文字列にはボーダーが存在しないため、早期に 0 を出力して処理をスキップしています。

  ソースコード

import sys
from math import gcd

def compute_failure(s):
    n = len(s)
    fail = [0] * n
    k = 0
    for i in range(1, n):
        while k > 0 and s[k] != s[i]:
            k = fail[k - 1]
        if s[k] == s[i]:
            k += 1
        fail[i] = k
    return fail

def solve():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    Q = int(tokens[idx]); idx += 1
    out = []
    for _ in range(Q):
        s = tokens[idx]; idx += 1
        n = len(s)
        if n <= 1:
            out.append('0')
            continue
        fail = compute_failure(s)
        # Collect all border lengths by following the failure chain from fail[n-1]
        borders = []
        v = fail[n - 1]
        while v > 0:
            borders.append(v)
            v = fail[v - 1]
        k = len(borders)
        if k == 0:
            out.append('0')
        elif k == 1:
            out.append(str(borders[0]))
        else:
            # borders are in decreasing order, reverse to get ascending
            borders.reverse()
            # Compute gcd of consecutive differences
            g = 0
            for i in range(1, k):
                g = gcd(g, borders[i] - borders[i - 1])
            out.append(str(g))
    sys.stdout.write('\n'.join(out) + '\n')

solve()

---

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