解题思路

“幸运字符串”指长度为偶数且前半部分与后半部分完全相同（空串也算）。 把 ? 看作可变的通配符：当成对字符都已知且不同，才 必定冲突；若有 ? 或相同，则能被补成相同。

错误回顾：我之前用了“对半长度 k 的可行性关于 k 单调”的假设做二分，但该假设是假的。样例 jum??ump 中，k=3 不可行而 k=4 可行，即并不单调，因此二分会错。

正确做法（线性滑窗 + 枚举间距）：

• 枚举所有半长 k = n//2 … 1（从大到小，找到就返回）。
• 对固定 k，构造冲突数组 bad[p]=1 当且仅当 s[p] 与 s[p+k] 都已知且不同；否则 bad[p]=0（含有 ? 视为可匹配）。 这里 p=0..n-k-1。
• 在 bad 上用长度为 k 的滑动窗口判断是否存在和为 0 的区间；若有，则存在长度 2k 的幸运子串。
• 若所有 k 都不行，则答案为 0（空串）。

该算法对每个 k 只做一次线性扫描，整体 O(n^2)，在 |s|≤5000 下完全可行。

复杂度分析

• 枚举 k 共 O(n) 次；每次构造 bad 并滑窗各 O(n)。
• 总时间复杂度 O(n^2)；空间复杂度 O(n)。

代码实现

Python

# -*- coding: utf-8 -*-
import sys

def max_lucky_length(s: str) -> int:
    n = len(s)
    # 从大到小枚举半长 k
    for k in range(n // 2, 0, -1):
        m = n - k
        bad = [0] * m  # bad[p]=1 表示 s[p] 与 s[p+k] 已知且不同
        for p in range(m):
            a, b = s[p], s[p + k]
            if a != '?' and b != '?' and a != b:
                bad[p] = 1
        # 长度为 k 的滑动窗口，找是否存在和为 0 的区间
        curr = sum(bad[:k])
        if curr == 0:
            return 2 * k
        for i in range(1, m - k + 1):
            curr += bad[i + k - 1] - bad[i - 1]
            if curr == 0:
                return 2 * k
    return 0  # 空串

if __name__ == "__main__":
    s = sys.stdin.readline().strip()
    print(max_lucky_length(s))

Java

// Java 17
import java.io.*;
import java.util.*;

public class Main {

    // 计算最大幸运值
    static int maxLuckyLength(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        // 从大到小枚举半长 k
        for (int k = n / 2; k >= 1; k--) {
            int m = n - k;
            int[] bad = new int[m]; // bad[p]=1 表示 s[p] 与 s[p+k] 已知且不同
            for (int p = 0; p < m; p++) {
                char a = s[p], b = s[p + k];
                if (a != '?' && b != '?' && a != b) bad[p] = 1;
            }
            // 长度为 k 的滑动窗口检查是否存在和为 0 的区间
            int curr = 0;
            for (int i = 0; i < k; i++) curr += bad[i];
            if (curr == 0) return 2 * k;
            for (int i = 1; i <= m - k; i++) {
                curr += bad[i + k - 1] - bad[i - 1];
                if (curr == 0) return 2 * k;
            }
        }
        return 0; // 空串
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        System.out.println(maxLuckyLength(s));
    }
}

C++

// g++ -std=c++17 -O2
#include <bits/stdc++.h>
using namespace std;

// 计算最大幸运值
int maxLuckyLength(const string &s) {
    int n = (int)s.size();
    // 从大到小枚举半长 k
    for (int k = n / 2; k >= 1; --k) {
        int m = n - k;
        vector<int> bad(m, 0); // bad[p]=1 表示 s[p] 与 s[p+k] 已知且不同
        for (int p = 0; p < m; ++p) {
            char a = s[p], b = s[p + k];
            if (a != '?' && b != '?' && a != b) bad[p] = 1;
        }
        // 长度为 k 的滑动窗口，找是否存在和为 0 的区间
        int curr = 0;
        for (int i = 0; i < k; ++i) curr += bad[i];
        if (curr == 0) return 2 * k;
        for (int i = 1; i <= m - k; ++i) {
            curr += bad[i + k - 1] - bad[i - 1];
            if (curr == 0) return 2 * k;
        }
    }
    return 0; // 空串
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if (getline(cin, s)) {
        cout << maxLuckyLength(s) << "\n";
    }
    return 0;
}

题目内容

幸运字符串:如果它的长度是偶数并且前一半与后一半完全一致，例如 $"abcabc”,"aaaa"$，特别地，空字符串 " " 也被认为是幸运字符串。

一个字符串的幸运值被定义为它的所有子串中，最长的幸运字符子串的长度。

例如在字符串 $"abbc"$ 中，它的子串为 $["abbc","abb","bbc","ab","bb","bc","a","b","c",”]$，而其中幸运字符子串为 $["bb",$" "$]$，所以 $"abbc"$ 的幸运值为 $"bb"$ 的长度,即 $"abbc”$ 的幸运值为 $2$ 。

多多发现了一张古老的魔法卷轴，上面写有一个由 $a-z$ 组成的字符串，其中某些字符因为时间久远已经无法辨认，无法辨认的字符使用 “$?$" 表示。魔法卷轴的等级由它上面记载的字符串的幸运值决定，多多希望为每个无法辨认的字符 "$?$" 填入一个字母 $(a-z)$ ,使得整个字符串的幸运值最大。

例如在字符串 $"aa?ab"$ 中，可以将 $"?"$ 替换成 $"a"$，这样填充形成新字符串 $"aaaab"$ ，其最长幸运字符子串为 $"aaaa"$ ，幸运值为 $4$ 。

请为多多计算一下填充后的字符串最大可能的幸运值是多少?

输入描述

共一行，包括多多在魔法卷轴上发现的字符串 $s$ ，其中每个字符均为 $a-z$ 或者 $?$ 之一，$?$ 表示无法辨认的字符。字符串长度 $|s|$ 满足 $1 ≤|s|≤ 5000$

输出描述

共 $1$ 行，包含一个整数，表示填充后的字符串最大可能的幸运值

样例1

输入

aaaaa

输出

4

说明

子串中最长的幸运字符串为 $aaaa$ ，长度为 $4$

样例2

输入

jum??ump

输出

8

说明

可以将字符串填充为 $jumpjump$ ，其本身就为幸运字符串，长度为 $8$

样例3

输入

dj?aaaaam

输出

6

说明

可以将字符串填充为 $djaaaaaam$ ，子串中最长的幸运字符串为 $aaaaaa$ ，长度为 $6$