题目链接

字符串奇偶性问题

题目描述

给定一个长度为 的字符串 ，以及一个整数 。我们需要对 的所有长度为 的子串进行一种变换，并统计变换后能产生多少种不同的新字符串。

变换规则如下：对于一个子串，将其所有奇数位（1-indexed）的字符按字典序升序排列，所有偶数位的字符按字典序降序排列，然后将这两部分拼接起来形成新的字符串。

思路分析

直接遍历所有 个子串，并对每个子串进行 的排序和变换，总时间复杂度为 ，在 较大时会超时。

我们可以发现，变换后的结果仅取决于子串中 奇数位字符的多重集 和 偶数位字符的多重集，而与它们的原始相对位置无关。例如，子串 "aBc" 和 "cBa" 的奇数位字符集都是 {a, c}，偶数位都是 {B}，因此它们会变换成同一个新字符串。

这个特性使得我们可以使用滑动窗口结合字符串哈希来优化。我们不必每次都生成变换后的字符串，而是可以为每个子串的“状态”计算一个哈希值，然后统计有多少种不同的哈希值。这里的“状态”就是指子串的奇偶位字符多重集。

我们可以用一个频率映射（计数数组）来表示一个字符多重集，并为这个频率映射计算一个多项式哈希值：。

我们的滑动窗口需要维护两个哈希值： 和 ，分别对应当前窗口内奇数位和偶数位字符集的哈希。当窗口从 S[i:i+k] 向右滑动一格到 S[i+1:i+k+1] 时，哈希值的变化如下：

  1. 移除 S[i]: S[i] 是原窗口的第1位（奇数），因此从 中减去它的哈希贡献。
  2. 交换角色: 原窗口中的偶数位字符，在新窗口中都移动到了奇数位；原窗口中的奇数位字符（除了S[i]），在新窗口中都移动到了偶数位。这个过程等效于交换 和 的值。
  3. 加入 S[i+k]: S[i+k] 是新窗口的第 位。根据 的奇偶性，将其哈希贡献加入到新的 或 中。

每一步的哈希更新都可以在 内完成。为了避免哈希碰撞，我们采用双哈希技术，即使用两组不同的模数和底数计算两对哈希值，并将这四个值作为一个元组存入集合中进行去重。

最终，集合的大小就是不同新字符串的数量。

代码

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <tuple>
#include <algorithm>

using namespace std;

// 字符到整数的映射
int char_to_int(char c) {
    if (islower(c)) return c - 'a';
    return c - 'A' + 26;
}

const long long M1 = 1e9 + 7, P1 = 53;
const long long M2 = 1e9 + 9, P2 = 59;
vector<long long> p1_pow, p2_pow;

void precompute_powers(int max_val) {
    p1_pow.resize(max_val);
    p2_pow.resize(max_val);
    p1_pow[0] = p2_pow[0] = 1;
    for (int i = 1; i < max_val; ++i) {
        p1_pow[i] = (p1_pow[i - 1] * P1) % M1;
        p2_pow[i] = (p2_pow[i - 1] * P2) % M2;
    }
}

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    long long h1_odd = 0, h1_even = 0;
    long long h2_odd = 0, h2_even = 0;

    for (int i = 0; i < k; ++i) {
        int char_idx = char_to_int(s[i]);
        if ((i + 1) % 2 != 0) { // 奇数位
            h1_odd = (h1_odd + p1_pow[char_idx]) % M1;
            h2_odd = (h2_odd + p2_pow[char_idx]) % M2;
        } else { // 偶数位
            h1_even = (h1_even + p1_pow[char_idx]) % M1;
            h2_even = (h2_even + p2_pow[char_idx]) % M2;
        }
    }

    set<tuple<long long, long long, long long, long long>> unique_states;
    unique_states.insert({h1_odd, h1_even, h2_odd, h2_even});

    for (int i = 0; i < n - k; ++i) {
        // 1. 移除 s[i] (原窗口第1位，奇数)
        int old_char_idx = char_to_int(s[i]);
        h1_odd = (h1_odd - p1_pow[old_char_idx] + M1) % M1;
        h2_odd = (h2_odd - p2_pow[old_char_idx] + M2) % M2;

        // 2. 交换角色
        swap(h1_odd, h1_even);
        swap(h2_odd, h2_even);

        // 3. 加入 s[i+k] (新窗口第k位)
        int new_char_idx = char_to_int(s[i + k]);
        if (k % 2 != 0) { // k是奇数，新字符在奇数位
            h1_odd = (h1_odd + p1_pow[new_char_idx]) % M1;
            h2_odd = (h2_odd + p2_pow[new_char_idx]) % M2;
        } else { // k是偶数，新字符在偶数位
            h1_even = (h1_even + p1_pow[new_char_idx]) % M1;
            h2_even = (h2_even + p2_pow[new_char_idx]) % M2;
        }
        
        unique_states.insert({h1_odd, h1_even, h2_odd, h2_even});
    }

    cout << unique_states.size() << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute_powers(52);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.HashSet;
import java.util.Objects;
import java.util.Scanner;
import java.util.Set;

public class Main {

    static final long M1 = 1_000_000_007, P1 = 53;
    static final long M2 = 1_000_000_009, P2 = 59;
    static long[] p1Pow, p2Pow;

    static class HashState {
        long h1Odd, h1Even, h2Odd, h2Even;

        public HashState(long h1Odd, long h1Even, long h2Odd, long h2Even) {
            this.h1Odd = h1Odd;
            this.h1Even = h1Even;
            this.h2Odd = h2Odd;
            this.h2Even = h2Even;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            HashState hashState = (HashState) o;
            return h1Odd == hashState.h1Odd && h1Even == hashState.h1Even &&
                   h2Odd == hashState.h2Odd && h2Even == hashState.h2Even;
        }

        @Override
        public int hashCode() {
            return Objects.hash(h1Odd, h1Even, h2Odd, h2Even);
        }
    }

    private static int charToInt(char c) {
        if (c >= 'a' && c <= 'z') return c - 'a';
        return c - 'A' + 26;
    }

    private static void precomputePowers(int maxVal) {
        p1Pow = new long[maxVal];
        p2Pow = new long[maxVal];
        p1Pow[0] = p2Pow[0] = 1;
        for (int i = 1; i < maxVal; i++) {
            p1Pow[i] = (p1Pow[i - 1] * P1) % M1;
            p2Pow[i] = (p2Pow[i - 1] * P2) % M2;
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s = sc.next();

        long h1Odd = 0, h1Even = 0;
        long h2Odd = 0, h2Even = 0;

        for (int i = 0; i < k; i++) {
            int charIdx = charToInt(s.charAt(i));
            if ((i + 1) % 2 != 0) { // Odd
                h1Odd = (h1Odd + p1Pow[charIdx]) % M1;
                h2Odd = (h2Odd + p2Pow[charIdx]) % M2;
            } else { // Even
                h1Even = (h1Even + p1Pow[charIdx]) % M1;
                h2Even = (h2Even + p2Pow[charIdx]) % M2;
            }
        }

        Set<HashState> uniqueStates = new HashSet<>();
        uniqueStates.add(new HashState(h1Odd, h1Even, h2Odd, h2Even));

        for (int i = 0; i < n - k; i++) {
            int oldCharIdx = charToInt(s.charAt(i));
            h1Odd = (h1Odd - p1Pow[oldCharIdx] + M1) % M1;
            h2Odd = (h2Odd - p2Pow[oldCharIdx] + M2) % M2;
            
            long temp1 = h1Odd; h1Odd = h1Even; h1Even = temp1;
            long temp2 = h2Odd; h2Odd = h2Even; h2Even = temp2;

            int newCharIdx = charToInt(s.charAt(i + k));
            if (k % 2 != 0) {
                h1Odd = (h1Odd + p1Pow[newCharIdx]) % M1;
                h2Odd = (h2Odd + p2Pow[newCharIdx]) % M2;
            } else {
                h1Even = (h1Even + p1Pow[newCharIdx]) % M1;
                h2Even = (h2Even + p2Pow[newCharIdx]) % M2;
            }
            
            uniqueStates.add(new HashState(h1Odd, h1Even, h2Odd, h2Even));
        }

        System.out.println(uniqueStates.size());
    }

    public static void main(String[] args) {
        precomputePowers(52);
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

import sys

M1, P1 = 10**9 + 7, 53
M2, P2 = 10**9 + 9, 59
P1_POW, P2_POW = [], []

def precompute_powers(max_val):
    global P1_POW, P2_POW
    P1_POW = [1] * max_val
    P2_POW = [1] * max_val
    for i in range(1, max_val):
        P1_POW[i] = (P1_POW[i - 1] * P1) % M1
        P2_POW[i] = (P2_POW[i - 1] * P2) % M2

def char_to_int(c):
    if 'a' <= c <= 'z':
        return ord(c) - ord('a')
    else:
        return ord(c) - ord('A') + 26

def solve():
    n, k = map(int, sys.stdin.readline().split())
    s = sys.stdin.readline().strip()

    h1_odd, h1_even = 0, 0
    h2_odd, h2_even = 0, 0

    for i in range(k):
        char_idx = char_to_int(s[i])
        if (i + 1) % 2 != 0:  # Odd
            h1_odd = (h1_odd + P1_POW[char_idx]) % M1
            h2_odd = (h2_odd + P2_POW[char_idx]) % M2
        else:  # Even
            h1_even = (h1_even + P1_POW[char_idx]) % M1
            h2_even = (h2_even + P2_POW[char_idx]) % M2
            
    unique_states = {(h1_odd, h1_even, h2_odd, h2_even)}

    for i in range(n - k):
        old_char_idx = char_to_int(s[i])
        h1_odd = (h1_odd - P1_POW[old_char_idx] + M1) % M1
        h2_odd = (h2_odd - P2_POW[old_char_idx] + M2) % M2

        h1_odd, h1_even = h1_even, h1_odd
        h2_odd, h2_even = h2_even, h2_odd

        new_char_idx = char_to_int(s[i + k])
        if k % 2 != 0:
            h1_odd = (h1_odd + P1_POW[new_char_idx]) % M1
            h2_odd = (h2_odd + P2_POW[new_char_idx]) % M2
        else:
            h1_even = (h1_even + P1_POW[new_char_idx]) % M1
            h2_even = (h2_even + P2_POW[new_char_idx]) % M2
            
        unique_states.add((h1_odd, h1_even, h2_odd, h2_even))
        
    print(len(unique_states))


def main():
    precompute_powers(52)
    try:
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：滑动窗口、字符串哈希（双哈希）
  • 时间复杂度：对于每组测试数据，初始化第一个窗口的哈希值需要 ，之后进行 次滑动，每次更新哈希值需要 。因此总时间复杂度为 。
  • 空间复杂度：。在最坏情况下，每个子串都可能产生一个独一无二的新字符串，因此存储哈希值的集合大小可能达到 。