可镜像子串问题

题目分析

给定一个长度为$n$的字符串$s$，要求计算其中有多少个长度大于$1$的子串是可镜像的。所谓可镜像子串，满足以下两个条件：

1. 回文串：从左到右和从右到左的顺序相同。
2. 垂直对称轴的字符：每个字符必须是有垂直对称轴的大写字母，具体包括'A', 'H', 'I', 'M', 'O', 'T', 'U', 'V', 'W', 'X', 'Y'。

解题思路

我们可以将问题拆解为以下几个步骤：

1. 检查字符是否符合镜像要求：我们可以通过预定义一个集合来快速判断某个字符是否属于镜像字符集合。
2. 判断回文：判断一个子串是否是回文串。
3. 枚举所有子串：遍历所有长度大于1的子串，逐一判断它们是否满足上述两个条件。如果满足条件，则计数。

步骤详细描述：

1. 遍历所有子串：我们需要遍历字符串中的每一个可能的子串。对于每一对起始和结束位置，提取子串并检查它是否符合镜像和回文条件。
2. 回文判断：对于每个子串，通过双指针法（从两端往中间逼近）判断其是否是回文串。
3. 镜像字符判断：对于每个回文子串，检查其中的每个字符是否都属于垂直对称的字符集。

复杂度分析

• 时间复杂度：由于我们需要枚举所有的子串并检查每个子串是否满足条件，对于长度为$n$的字符串，子串的数量为$O(n^2)$，而每次检查子串需要$O(n)$的时间（检查回文和镜像字符）。因此，整体时间复杂度为$O(n^3)$。
• 空间复杂度：额外的空间复杂度主要用于存储镜像字符的集合和一些辅助变量，空间复杂度为$O(1)$（忽略存储输入字符串所需的空间）。

代码实现

Python代码

def check(c):
    # 判断字符是否为垂直对称字符
    return c in "AHIMOTUVWXY"

def is_palindrome(s):
    # 判断字符串是否为回文串
    return s == s[::-1]

def count_mirror_substrings(s):
    n = len(s)
    count = 0
    
    # 枚举所有长度大于1的子串
    for i in range(n):
        for j in range(i+1, n):
            sub = s[i:j+1]
            
            # 如果是回文且所有字符都为垂直对称字符
            if is_palindrome(sub) and all(check(c) for c in sub):
                count += 1
    
    return count

# 输入并输出结果
s = input().strip()
print(count_mirror_substrings(s))

Java代码

import java.util.*;

public class Main {
    // 判断字符是否为垂直对称字符
    public static boolean check(char c) {
        return c == 'A' || c == 'H' || c == 'I' || c == 'M' || c == 'O' || c == 'T' ||
               c == 'U' || c == 'V' || c == 'W' || c == 'X' || c == 'Y';
    }
    
    // 判断字符串是否为回文串
    public static boolean isP(String s) {
        int L = 0;
        int R = s.length() - 1;
        while (L <= R) {
            if (s.charAt(L) != s.charAt(R) || !check(s.charAt(L))) {
                return false;
            }
            L++;
            R--;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int n = s.length();
        int count = 0;
        
        // 枚举所有长度大于1的子串
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                String sub = s.substring(i, j + 1);
                if (isP(sub)) {
                    count++;
                }
            }
        }
        System.out.println(count); 
    }
}

C++代码

#include <iostream>
#include <string>
using namespace std;

// 判断字符是否为垂直对称字符
bool check(char c) {
    return c == 'A' || c == 'H' || c == 'I' || c == 'M' || c == 'O' || c == 'T' ||
           c == 'U' || c == 'V' || c == 'W' || c == 'X' || c == 'Y';
}

// 判断字符串是否为回文串
bool is_palindrome(const string &s) {
    int L = 0, R = s.length() - 1;
    while (L <= R) {
        if (s[L] != s[R] || !check(s[L])) {
            return false;
        }
        L++;
        R--;
    }
    return true;
}

int main() {
    string s;
    cin >> s;
    int n = s.length();
    int count = 0;

    // 枚举所有长度大于1的子串
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            string sub = s.substr(i, j - i + 1);
            if (is_palindrome(sub)) {
                count++;
            }
        }
    }

    cout << count << endl;
    return 0;
}

题目内容

小美有一个长度为$n$的字符串$s$，她想知道这个字符串有多少个长度大于$1$的子串是可镜像的。

可镜像的意思是:一个字符串是回文串，且其中每个字符都有垂直对称轴。

[回文串]一个字符串被称作回文串，当且仅当这个字符串从左往右读和从右往左读是相同的。

有垂直对称轴的大写字母:'$A$','$H$','$T$', '$M$', '$O$', '$T$', '$U$','$V$', '$W$', '$X$', '$Y$'。

输入描述

输入一个长度为$n$的字符串$s$，字符串中仅包含大写字母。

$1≦n≦100$

输出描述

输出一个整数，表示字符串$s$中长度大于$1$的可镜像的子串的数量

样例1

输入

AHHAMTT

输出

3

说明

一共$3$个长度大于$1$的可镜像的子串:"$HH$","$AHHA$","$TT$"