小红的项链

[题目链接](https://www.nowcoder.com/practice/15c776baad3e4ebe995576b4725fe6ce)

思路

给定一条长度为 （偶数）的环形项链，要在对称位置切一刀，分成两条长度为 的链，使两条链的相似度（对应位置字符相同的数量）最大。

转化为滑动窗口

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

在位置 处切割，得到的两条链分别是：

  • 链 1：
  • 链 2：

（下标均对 取模）

两条链的相似度就是：

$$

定义辅助数组 ，则切割位置 的相似度等于 数组中从 开始、长度为 的连续段之和。

这就是一个环形数组上固定窗口大小为 的滑动窗口求最大值问题，只需 即可解决。

算法步骤

  1. 构建 数组：遍历每个位置 ，若 则为 1，否则为 0。
  2. 计算初始窗口（位置 到 ）的和。
  3. 滑动窗口：每次加入窗口右端新元素，移除左端旧元素，更新最大值。
  4. 遍历所有 个切割位置后输出最大值。

样例演示

输入 cabcdabc，，。
0 c d 0
1 a a 1
2 b b 1
3 c c 1
4 d c 0
5 a a 1
6 b b 1
7 c c 1

切割位置 时，窗口为 ，和为 3。

切割位置 时，窗口为 ，和为 3。

最大相似度为 3。

复杂度分析

  • 时间复杂度：，构建 match 数组和滑动窗口各遍历一次。
  • 空间复杂度：，存储 match 数组。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    int half = n / 2;
    vector<int> match(n);
    for(int i = 0; i < n; i++){
        match[i] = (s[i] == s[(i + half) % n]) ? 1 : 0;
    }
    int cur = 0;
    for(int j = 0; j < half; j++){
        cur += match[j];
    }
    int ans = cur;
    for(int i = 1; i < n; i++){
        cur += match[(i + half - 1) % n];
        cur -= match[i - 1];
        ans = max(ans, cur);
    }
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();
        int half = n / 2;
        int[] match = new int[n];
        for (int i = 0; i < n; i++) {
            match[i] = (s.charAt(i) == s.charAt((i + half) % n)) ? 1 : 0;
        }
        int cur = 0;
        for (int j = 0; j < half; j++) {
            cur += match[j];
        }
        int ans = cur;
        for (int i = 1; i < n; i++) {
            cur += match[(i + half - 1) % n];
            cur -= match[i - 1];
            ans = Math.max(ans, cur);
        }
        System.out.println(ans);
    }
}