题目链接

小红的项链

题目描述

给定一个长度为 的环形字符串（ 是偶数）。我们需要在两个对称的位置切开项链，得到两条长度相等（均为 ）的链。

我们的目标是找到一种切割方式，使得得到的两条链的相似度最大。相似度定义为：两条链在相同位置上拥有相同字符的数量。

解题思路

这是一个在所有可能的切割方式中寻找最优解的问题。我们可以通过分析问题结构，将其转化为一个经典的滑动窗口求最大和的问题。

将问题线性化

设项链字符串为 ，长度为 ，令 。

一次切割由一个起始位置决定。如果我们选择在第 个字符和第 个字符之间切下（索引从 0 开始，环形处理），那么得到的第一条链就是从索引 开始，长度为 的子串。对称的切割点则在第 和第 个字符之间。

这样，对于一个从索引 开始的切割（我们称之为切割方案 ），我们得到两条链：

  • 链1：由原项链中索引为 的字符顺序组成。
  • 链2：由原项链中索引为 的字符顺序组成。

(所有索引都需要对 取模以处理环形情况)

相似度就是比较这两条链，对应位置字符相同的数量。即，对于切割方案 ，其相似度 为：

其中 是艾佛森括号，条件为真时值为 1，否则为 0。

转化为滑动窗口问题

直接枚举所有切割方案并计算相似度是可行的。总共有 种不同的切割方案（在 处切割和在 处切割是等价的），每种方案的相似度计算需要 的时间，总时间复杂度为 。对于 的数据规模，这个复杂度是可以接受的，但我们可以做得更好。

我们可以预处理一个“匹配数组”来优化计算。

  1. 构建匹配数组：

    创建一个长度为 的辅助数组 match。对于项链上的每一个位置 （从 0 到 ），我们比较它和它对称位置上的字符是否相同。

    • match[k] = 1 如果 s[k] == s[(k+m)%n]
    • match[k] = 0 如果 s[k] != s[(k+m)%n]

    这个数组的构建需要 的时间。

  2. 关联相似度与匹配数组：

    观察相似度的计算公式，我们可以发现，切割方案 的相似度 正是 match 数组中从索引 开始，长度为 的一个子数组（环形）的和。

  3. 滑动窗口求最大和：

    现在问题就变成了：在一个长度为 的环形整数数组 match 中，找到一个长度为 的连续子数组，使其和最大。

    这是一个经典的滑动窗口问题，可以在 时间内解决：

    a. 首先计算出第一个窗口（索引 到 ）的和。

    b. 然后将窗口向右滑动。每次滑动，减去离开窗口的旧元素，加上进入窗口的新元素，从而在 的时间内更新窗口的和。

    c. 在每次滑动后，都用当前窗口的和来更新最大值。

最终算法步骤

  1. 读入字符串 ，获取其长度 ，计算 。
  2. 创建大小为 的 match 数组，根据 s[k] == s[(k+m)%n] 填充 0 或 1。
  3. 使用滑动窗口算法，在 match 数组上（将其视为环形）找到长度为 的子数组的最大和。
  4. 这个最大和就是答案。

代码

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;

    int n = s.length();
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    int m = n / 2;

    vector<int> match(n);
    for (int i = 0; i < n; ++i) {
        if (s[i] == s[(i + m) % n]) {
            match[i] = 1;
        } else {
            match[i] = 0;
        }
    }

    long long current_similarity = 0;
    for (int i = 0; i < m; ++i) {
        current_similarity += match[i];
    }

    long long max_similarity = current_similarity;

    for (int i = 1; i < n; ++i) {
        current_similarity -= match[i - 1];
        current_similarity += match[(i + m - 1) % n];
        if (current_similarity > max_similarity) {
            max_similarity = current_similarity;
        }
    }

    cout << max_similarity << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        int n = s.length();
        if (n == 0) {
            System.out.println(0);
            return;
        }
        int m = n / 2;

        int[] match = new int[n];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == s.charAt((i + m) % n)) {
                match[i] = 1;
            } else {
                match[i] = 0;
            }
        }

        long currentSimilarity = 0;
        for (int i = 0; i < m; i++) {
            currentSimilarity += match[i];
        }

        long maxSimilarity = currentSimilarity;

        for (int i = 1; i < n; i++) {
            currentSimilarity -= match[i - 1];
            currentSimilarity += match[(i + m - 1) % n];
            if (currentSimilarity > maxSimilarity) {
                maxSimilarity = currentSimilarity;
            }
        }

        System.out.println(maxSimilarity);
    }
}

import sys

def solve():
    s = sys.stdin.readline().strip()
    n = len(s)
    if n == 0:
        print(0)
        return
    
    m = n // 2

    match = [0] * n
    for i in range(n):
        if s[i] == s[(i + m) % n]:
            match[i] = 1

    current_similarity = sum(match[0:m])
    max_similarity = current_similarity

    for i in range(1, n):
        # Slide the window
        current_similarity -= match[i - 1]
        current_similarity += match[(i + m - 1) % n]
        if current_similarity > max_similarity:
            max_similarity = current_similarity
            
    print(max_similarity)

solve()

算法及复杂度

  • 算法：滑动窗口
  • 时间复杂度：。构建 match 数组需要 ，滑动窗口遍历一次也需要 。
  • 空间复杂度：。需要一个额外的 match 数组来存储中间结果。