形式化题目

给定长度为 $n$ 的字符串 $s$，字符取自小写字母与通配符 ?。每个 ? 可以独立替换成任意小写字母。求替换后 $s$ 里最长的串联重复子串长度；不存在时输出 0。

串联重复指长度 $2q$ 的字符串，前一半与后一半逐位相同。它只要作为连续子串出现即可，不必覆盖整个串。形式化地，要求

其中 $\operatorname{compat}(i, j)$ 表示两位在替换后可以相同，即 $s[i] = s[j]$，或 $s[i] = \texttt{?}$，或 $s[j] = \texttt{?}$。

把通配符吸收进 $\operatorname{compat}$ 之后，题目不再有构造成分，只剩「找最长的、前后两半逐位相容的区间」。

约束：$1 \leqslant t \leqslant 1000$，$1 \leqslant n \leqslant 5000$，所有测试串长度之和 $\leqslant 5000$，时间限制 2 秒。

暴力解法

思路

最直接的做法枚举三样东西：半长 $q$、起点 $st$、以及两半内部的第 $k$ 位。三次枚举共 $O(n^3)$，满规模约 $10^{11}$ 次比较，不可行。

下面这份代码把第三层枚举消掉了，只保留 $O(n^2)$：固定 $q$ 之后，所有被比较的位置对都是 $(i,\ i+q)$ 这种固定间距的形式，可以一次算完整条数组。

对固定 $q$ 定义相容数组

于是「存在起点 $st$ 使两半全相容」等价于「$b_q[st..st+q-1]$ 全是 1」。再用一个递推累计以 $i$ 结尾的连续 1 长度：$b_q[i] = 1$ 时 $f[i] = f[i-1] + 1$，否则 $f[i] = 0$。某个 $f[i]$ 一旦达到 $q$，就说明找到了长度为 $2q$ 的串联重复。

以 $s = \texttt{zaabaabz}$、$q = 3$ 为例，比较的位置对是 $(0,3), (1,4), \ldots, (4,7)$：

$b_3[1..3]$ 全为 1，对应子串 $s[1..6] = \texttt{aabaab}$，长度 $2q = 6$，正是答案。

这里有一处容易写错的地方：递推只和 $b_q$ 的前一位比较，不要再拿 $s[i]$ 和 $s[i-q]$ 比。$+q$ 的比较在 $b_q$ 的定义里已经做完了，重复比较会把下标关系搞乱。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59"""
很容易想到 n^3 的算法


采用思维转化:

问题: f[i] 表示第i个元素为结尾的时候, 定长为q, (i前面的每个元素j 都和j+q想等的)连续的最大长度是多少

f[i] = f[i - 1] + 1 if a[i] == a[i - q]
f[i] = 0 if a[i] != a[i - q]

然后发现一重要的数学性质: 

    if f[i] == q: 

  [i-q+1] [] [i] q=3

  则 i-q+1 对应  i-q+1+q = i+1

    则正好从i-q+1 -> i+q 是一个 Tandem Repeats

当定长为q的时候

f[i] = 
"""

import sys

def check(s:str,q):
    same = lambda a,b : a == b or b == '?' or a == '?'
    # 转化成new array b 
    b = [ 1 if same(s[i], s[i+q]) else 0  for i in range(0,len(s)-q)]
    # print(b)
    c = [0] * len(b)
    for i in range(len(b)):
        if b[i] == 0:
            c[i] = 0
        else:
            c[i] = c[i-1] + 1
            if c[i] >= q:
                return q
    return 0


def solve(data):


    for s in data:
        # print(s,len(s)//2)
        t =  [check(s,q) for q in range(1,len(s)//2+1)]
        # print(t)
        ans = max(t,default=0)
        print(ans*2)



if __name__ == "__main__":
    n,*data = sys.stdin.buffer.read().decode().split()
    solve(data)

复杂度

外层 $q$ 有 $O(n)$ 个取值，每个 $q$ 建两个长度 $O(n)$ 的列表并各扫一遍，时间 $O(n^2)$，空间 $O(n)$。算法层面已经足够，满规模是 $1.2 \times 10^7$ 量级的基本操作。

瓶颈

瓶颈不在复杂度阶数，而在每次基本操作的代价。这份实现有三处代价都落在 Python 解释器上：

1. 每个 $q$ 都新建一个长度为 $n-q$ 的列表 b，列表推导里每一步是三次字符串比较加一次分支（a == b or b == '?' or a == '?'）。
2. 再新建一个同样长度的列表 c，用 Python 的 for 循环逐格写入，每格一次比较加一次赋值。
3. 外层 $q$ 从小到大枚举，必须把所有 $q$ 都算完才能 max，找不到任何提前退出的机会。

总长 5000 时，前两条合计约 $1.2 \times 10^7$ 次字节码调度。本地实测满规模 2～3 秒，超过 2 秒限制。

另外这份代码在 $n < 2$ 时直接崩溃：range(1, len(s)//2 + 1) 为空，max([]) 抛 ValueError。同理 c[i-1] 在 $i = 0$ 时取到的是 c[-1]，只因列表初始化为全 0 才恰好正确。

正解

思路

算法骨架不动，仍然是「枚举 $q$、构造相容数组、判连续 1」。要消除的只是解释器层的逐元素循环。手段是把整条数组压进一个整数，让内层运算由大整数的 C 实现完成。

第一步：用 bitmask 表示位置集合。 对每个字符 $c$ 建一个整数 $M_c$，第 $i$ 位为 1 当且仅当 $s[i] = c$。记 $Q = M_{\texttt{?}}$ 为通配符的位置集合。这样「$s[i]$ 等于某个字符」变成「第 $i$ 位为 1」，逐位比较变成整数的移位与按位与。

第二步：一次算出整条 $b_q$。 相容有三种情况，各对应一段位运算：

先说符号：$Q \gg q$ 是把通配符位置整体右移 $q$ 位，于是它的第 $i$ 位为 1 表示 $s[i+q] = \texttt{?}$；$M_c \mathrel{\&} (M_c \gg q)$ 的第 $i$ 位为 1 表示 $s[i] = s[i+q] = c$。整条式子合起来的意思是：第 $i$ 位为 1 当且仅当两位都是 ?、或有一边是 ?、或两边是同一个字母，正是 $\operatorname{compat}(i,\ i+q)$。一个 $q$ 只需要 $|\Sigma| + 2 \leqslant 29$ 次大整数运算，而不是 $n$ 次字符比较。

右移会在高位留下越界的残留位，所以最后要截断到 $[0,\ n-q)$：m &= (1 << (n - q)) - 1。

第三步：用倍增判连续 1。 令 $m$ 为 $b_q$ 的 bitmask。反复执行

执行一轮后，第 $i$ 位为 1 当且仅当原 $b_q[i-1..i]$ 全为 1；执行 $k$ 轮后，第 $i$ 位为 1 当且仅当原 $b_q[i-2^k+1..i]$ 全为 1。把 $L$ 倍增到不超过 $q$ 的最大 2 的幂，还差 $r = q - L$ 位，再补一次 $m \mathrel{\&}= m \gg r$，就能判定「是否存在长度 $q$ 的连续 1」。整个过程 $O(\log q)$ 次移位，不需要任何长度为 $q$ 的中间数组。

第四步：$q$ 从大到小枚举。 只关心最长的答案，所以从 $q = \lfloor n/2 \rfloor$ 递减，命中即停。再加一条剪枝：当前 $2q$ 已经不大于已知答案时直接跳出。

判据的正确性。 记条件为「$b_q[st..st+q-1]$ 全为 1」，目标为「$s[st..st+2q-1]$ 在替换后成为串联重复」，两个方向都要成立。

充分性（条件成立 $\Rightarrow$ 目标成立）：

• $b_q[st+k] = 1$ 说明 $\operatorname{compat}(st+k,\ st+k+q)$，即两位相等，或至少一边是 ?。
• 逐对处理：两位相等则不动；只有一边是 ? 就把 ? 换成另一边的字母；两边都是 ? 就都换成同一个字母。
• 每一对占据两个互不重叠的位置，替换之间不会冲突。
• 替换完成后两半逐位相同，子串成为长度 $2q$ 的串联重复。

必要性（目标成立 $\Rightarrow$ 条件成立）：

• 目标成立意味着存在一种替换使 $s[st+k] = s[st+k+q]$ 对所有 $0 \leqslant k < q$ 成立。
• 替换只能改动 ?，所以替换前这两位要么本来就相等，要么至少有一个是 ?。
• 这正是 $\operatorname{compat}(st+k,\ st+k+q)$，即 $b_q[st+k] = 1$；$k$ 取遍 $0..q-1$ 就得到 $b_q[st..st+q-1]$ 全为 1。

两个方向合起来，判据与目标严格等价。

为什么不会漏掉答案。 若某段 $b_q[st..st+q-1]$ 全为 1，递推从 $f[st] = 1$ 起每步加 1，必在 $i = st+q-1$ 处得到 $f[i] = q$；倍增法的语义与此一致，只是把「逐位加 1」换成了「按 2 的幂合并区间」。所以两者命中的 $q$ 集合完全相同。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84"""
题意: 问号可以替换成任意小写字母, 求最长的 Tandem Repeats (前半 == 后半) 的长度.

这是 main.py 的优化版 (原版 O(n^2) 的 Python 双层循环在 n=5000 时约 3~5s, 会 TLE).

沿用 main.py 里的数学结论:
    对固定的半长 q, 令
        b[i] = 1  if  s[i] 与 s[i+q] 相容 (相等, 或有一边是 '?')
        b[i] = 0  otherwise
    则 [st, st+2q) 是 Tandem Repeats  <=>  b[st .. st+q-1] 全是 1
    即: b 中必须存在一段长度 >= q 的连续 1.

    (对应 main.py 里的 f 递推: f[i] = f[i-1] + 1 if b[i] else 0,
     当 f[i] == q 时就找到了一个答案.
     注意是拿 b[i] 判断, 不是拿 a[i] 和 a[i-q] 比较 —— +q 的比较已经在 b 里做完了.)

优化点: 把两处 Python 级循环换成大整数位运算
    1. 每种字符出现的位置压成 bitmask, 则
           b = (?mask | (?mask >> q)) | Σ (letter_mask & (letter_mask >> q))
       一次位运算算出整排 b, 而不是 n 次字符比较.
    2. "是否存在长度 q 的连续 1" 用倍增法 m &= m >> L (L = 1,2,4,...),
       约 log q 次大整数移位, 而不是 q 次扫描.
    3. q 从大到小枚举, 找到即退出, 并加 2q <= ans 剪枝.

复杂度: 约 O(n^2 / wordsize * log n), 实际几乎全在 C 层.
"""

import sys


def has_run(m, q):
    """m 的第 i 位为 1 表示 b[i]==1; 判断是否存在长度 >= q 的连续 1."""
    L = 1
    while L * 2 <= q:
        m &= m >> L          # 现在第 i 位为 1  <=>  原 m[i-L+1 .. i] 全 1 (长度 2L)
        L *= 2
        if not m:
            return False
    r = q - L                # 还差 r 位, 再对齐一次
    if r:
        m &= m >> r
    return m != 0


def check_bits(n, qmask, letters, q):
    """判断半长 q 下是否存在 Tandem Repeats."""
    # 相容位置: 两边都是 '?' , 或者某一边是 '?' , 或者同字母
    m = qmask | (qmask >> q)
    for a in letters:
        m |= a & (a >> q)
    m &= (1 << (n - q)) - 1     # 只保留 0 .. n-q-1
    return bool(m) and has_run(m, q)


def solve(data):
    out = []
    for s in data:
        n = len(s)
        if n < 2:                       # 长度 <2 不可能有 tandem repeat
            out.append('0')
            continue

        # 每种字符出现在哪些位置: bit i 为 1 <=> s[i] == ch
        pos = {}
        for i, ch in enumerate(s):
            pos[ch] = pos.get(ch, 0) | (1 << i)
        qmask = pos.pop('?', 0)         # '?' 的位置
        letters = list(pos.values())

        ans = 0
        for q in range(n // 2, 0, -1):  # 从大到小枚举, 找到就能提前退出
            if 2 * q <= ans:
                break
            if check_bits(n, qmask, letters, q):
                ans = 2 * q
                break
        out.append(str(ans))

    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    _t, *data = sys.stdin.buffer.read().decode().split()
    solve(data)

复杂度

位运算版本的时间是 $O(n^2 \log n / w)$，$w$ 为大整数内部每个 digit 的位宽（CPython 为 30 位）。$n = 5000$ 时，一个整数占 167 个 digit，单个 $q$ 的 bitmask 构造约 $29 \times 167$ 次 digit 级运算，倍增判定最多 12 轮、约 $12 \times 167$ 次；再叠加「$q$ 递减、命中即停、$2q \leqslant ans$ 剪枝」，随机数据远早于 $q = n/2$ 就退出。空间为每字符一个 bitmask，$O(n)$ 位。

本地实测（$n = 5000$，两程序交错各跑 5 次取中位数）：

同一算法的骨架，只把内层从解释器搬到大整数运算，就有 30 倍以上的差距；main.py 单次最短也有 2.0 秒，仍在限制之外。在 Python 里评估「能不能过」时，$O(n^2)$ 这样的阶数只是下限，真正的判据是每步操作的实现代价。

总结

• 关键转化是固定半长 $q$，把「两半逐位比较」折成一条相容数组 $b_q$，原问题变成「$b_q$ 中是否存在长度 $q$ 的连续 1」。这一步把 $O(n^3)$ 降到 $O(n^2)$。
• 递推只用 $b_q$ 的前一位，不要重复拿 $s[i]$ 和 $s[i-q]$ 比较；$+q$ 的比较已经在 $b_q$ 里完成。
• 判据是充要条件，充分性靠「逐对替换互不冲突」，必要性靠「替换只影响 ?」，两个方向都成立才允许把答案交给它。
• main-optimize.py 的优化全部落在实现层，共四处：位置压成 bitmask 让整条 $b_q$ 一次算出、倍增法 $m \mathrel{\&}= m \gg L$ 把连续 1 判定压到 $O(\log q)$ 次移位、$q$ 从大到小枚举并命中即停、$2q \leqslant ans$ 剪枝。阶数没变，常数降了两个数量级。
• 边界：$n < 2$ 时答案为 0。main.py 在此处会因 max([]) 崩溃，main-optimize.py 已显式处理。
• 验证记录：以独立的 $O(n^3)$ 枚举为基准，main-optimize.py 通过 600 组随机数据对拍（字母表含 ab、abc?、a?、?、abcdefghij 等，长度 1～18），main.py 与 main-optimize.py 在 600 组长度 2～18 的数据上输出一致，另有多测试点 1200 个小用例全部正确。满规模计时见上表。未使用官方完整测试数据，也未在 PyPy 下计时。