题解 | #神秘串#

题目链接

神秘串

题目描述

给定一个仅由小写英文字母组成的字符串 $S$ ，长度为 $n$ 。设元音字母集合为 {a, e, i, o, u}，其余字母视为辅音。

定义元音回文串如下：设子串 $T = S[l..r]$ ，长度 $m=r-l+1$ 。

若对所有 $1 \le i \le m$ ，满足：若 $T_i$ 或 $T_{m-i+1}$ 为元音，则必须有 $T_i = T_{m-i+1}$ 。

则称 $T$ 为元音回文串。

注意：

对于一对对称位置 $(i, m-i+1)$ ，若两侧均为辅音，则无需相等。
若其中至少一侧为元音，则必须相等。

现在请你在 $S$ 的所有子串中找出最长的元音回文串，并输出其长度。

解题思路

这是一个广义回文串问题。标准的回文串要求对称位置的字符必须完全相等。而本题的“元音回文串”则定义了一个特殊的匹配规则：对于一对对称字符 $(c_1, c_2)$ ，它们匹配的条件是 c1 == c2 或者 c1 和 c2 都是辅音。

直接暴力枚举所有子串并检查其是否为元音回文串的复杂度为 $O(N^2)$ 或 $O(N^3)$ ，无法通过本题。

解决这类问题的经典方法是 Manacher 算法。标准 Manacher 算法可以在线性时间内找出字符串中最长的标准回文子串。我们可以通过修改其核心的字符比较逻辑，来适配本题定义的特殊匹配规则。

算法步骤

自定义匹配规则:

我们首先定义一个函数 match(c1, c2)，用来判断两个字符是否满足元音回文串的对称匹配要求。根据题意，match(c1, c2) 为真的条件是：
- c1 == c2
- 或者 (c1 不是元音且 c2 也不是元音)
预处理字符串:

和标准 Manacher 算法一样，我们将原始字符串 $S$ 改造为 $S'$ ，在每两个字符之间以及字符串首尾插入一个特殊的分隔符（如 #）。例如，"aba" 变为 "#a#b#a#"。这样做的好处是统一处理了奇数长度和偶数长度的回文串。
修改版 Manacher 算法:
- 我们创建一个数组 p，其中 p[i] 表示以 $S'[i]$ 为中心的最长元音回文串的半径。
- 我们遍历改造后的字符串 $S'$ ，计算每个位置的 p[i]。
- 为了实现线性时间复杂度，算法维护 center 和 max_right，max_right 是当前所有已发现的元音回文串所能达到的最右边界，center 是这个串的中心。
- 对于当前位置 i，如果它在 max_right 的覆盖范围内，我们可以利用其关于 center 的对称点 mirror 的信息来初始化一个最小的 p[i]，从而避免不必要的比较。
- 然后，我们从这个最小半径开始，不断向外扩展，只要 S' 中对称位置的字符满足我们自定义的 match 规则，就增加半径 p[i]。
- 每次计算完 p[i] 后，更新 center 和 max_right（如果需要），并记录下 p[i] 的最大值。
结果:

遍历完成后，p 数组中的最大值就是最长元音回文子串在原字符串 $S$ 中的长度。

这个修改版的 Manacher 算法保留了原算法的框架和线性时间复杂度特性，仅仅替换了核心的比较函数，从而能够解决本题。

代码

cpp
java
python

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

using namespace std;

bool is_vowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

bool match(char c1, char c2) {
    if (c1 == c2) return true;
    if (!is_vowel(c1) && !is_vowel(c2)) return true;
    return false;
}

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

    int n;
    cin >> n;
    string s;
    cin >> s;

    string t = "#";
    for (char c : s) {
        t += c;
        t += '#';
    }

    int len_t = t.length();
    vector<int> p(len_t, 0);
    int center = 0, max_right = 0;
    int max_len = 0;

    for (int i = 0; i < len_t; ++i) {
        int mirror = 2 * center - i;
        if (i < max_right) {
            p[i] = min(max_right - i, p[mirror]);
        }

        int l = i - (p[i] + 1);
        int r = i + (p[i] + 1);
        while (l >= 0 && r < len_t && match(t[l], t[r])) {
            p[i]++;
            l--;
            r++;
        }

        if (i + p[i] > max_right) {
            center = i;
            max_right = i + p[i];
        }
        max_len = max(max_len, p[i]);
    }

    cout << max_len << endl;

    return 0;
}

import java.util.Scanner;

public class Main {

    private static boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    private static boolean match(char c1, char c2) {
        if (c1 == c2) return true;
        if (c1 != '#' && c2 != '#' && !isVowel(c1) && !isVowel(c2)) return true;
        return false;
    }

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

        StringBuilder tBuilder = new StringBuilder("#");
        for (char c : s.toCharArray()) {
            tBuilder.append(c).append('#');
        }
        String t = tBuilder.toString();

        int lenT = t.length();
        int[] p = new int[lenT];
        int center = 0, maxRight = 0;
        int maxLen = 0;

        for (int i = 0; i < lenT; i++) {
            int mirror = 2 * center - i;
            if (i < maxRight) {
                p[i] = Math.min(maxRight - i, p[mirror]);
            }

            int l = i - (p[i] + 1);
            int r = i + (p[i] + 1);
            while (l >= 0 && r < lenT && match(t.charAt(l), t.charAt(r))) {
                p[i]++;
                l--;
                r++;
            }

            if (i + p[i] > maxRight) {
                center = i;
                maxRight = i + p[i];
            }
            maxLen = Math.max(maxLen, p[i]);
        }

        System.out.println(maxLen);
    }
}

import sys

def is_vowel(c):
    return c in "aeiou"

def match(c1, c2):
    if c1 == c2:
        return True
    if c1 != '#' and c2 != '#' and not is_vowel(c1) and not is_vowel(c2):
        return True
    return False

def main():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        s = sys.stdin.readline().strip()
    except (IOError, ValueError):
        return

    t = '#' + '#'.join(s) + '#'
    len_t = len(t)
    p = [0] * len_t
    center, max_right = 0, 0
    max_len = 0

    for i in range(len_t):
        mirror = 2 * center - i
        if i < max_right:
            p[i] = min(max_right - i, p[mirror])

        l, r = i - (p[i] + 1), i + (p[i] + 1)
        while l >= 0 and r < len_t and match(t[l], t[r]):
            p[i] += 1
            l -= 1
            r += 1

        if i + p[i] > max_right:
            center = i
            max_right = i + p[i]
        
        max_len = max(max_len, p[i])

    print(max_len)

main()

算法及复杂度

算法：修改版 Manacher 算法
时间复杂度： $O(N)$ ，其中 $N$ 是字符串 $S$ 的长度。Manacher 算法的每个字符只会被比较常数次。
空间复杂度： $O(N)$ ，用于存储改造后的字符串 $S'$ 和半径数组 $p$ 。