题解 | 统计回文

解题思路

本题要求在字符串 $A$ 中插入字符串 $B$ ，使得生成的新字符串是一个回文串。我们可以通过遍历所有可能的插入位置来解决这个问题。

关键点：

回文串的定义：正读和反读都相同的字符串。
插入位置的选择：可以在字符串 $A$ 的任意位置插入字符串 $B$ ，包括字符串的开头和结尾。
检查回文串：通过双指针方法检查生成的字符串是否为回文。

算法步骤：

遍历字符串 $A$ 的所有可能插入位置。
在每个位置插入字符串 $B$ ，生成新的字符串。
检查新字符串是否为回文，如果是，则计数加一。

代码

cpp
java
python

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

// 检查字符串是否为回文
bool isPalindrome(const string& str) {
    int left = 0;
    int right = str.length() - 1;
    while (left < right) {
        if (str[left] != str[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    string A, B;
    getline(cin, A);
    getline(cin, B);
    
    int count = 0;
    int lenA = A.length();
    
    // 遍历所有可能的插入位置
    for (int i = 0; i <= lenA; i++) {
        // 在A的第i个位置插入B
        string newString = A.substr(0, i) + B + A.substr(i);
        // 检查新字符串是否为回文
        if (isPalindrome(newString)) {
            count++;
        }
    }
    
    // 输出结果
    cout << count << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    // 检查字符串是否为回文
    private static boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        String A = sc.nextLine();
        String B = sc.nextLine();
        
        int count = 0;
        int lenA = A.length();
        
        // 遍历所有可能的插入位置
        for (int i = 0; i <= lenA; i++) {
            // 在A的第i个位置插入B
            String newString = A.substring(0, i) + B + A.substring(i);
            // 检查新字符串是否为回文
            if (isPalindrome(newString)) {
                count++;
            }
        }
        
        // 输出结果
        System.out.println(count);
        
        sc.close();
    }
}

def is_palindrome(s):
    return s == s[::-1]

A = input().strip()
B = input().strip()

count = 0
lenA = len(A)

# 遍历所有可能的插入位置
for i in range(lenA + 1):
    # 在A的第i个位置插入B
    new_string = A[:i] + B + A[i:]
    # 检查新字符串是否为回文
    if is_palindrome(new_string):
        count += 1

# 输出结果
print(count)

算法及复杂度

算法：遍历插入位置并检查回文
时间复杂度： $O(n^2)$ ，其中 $n$ 是字符串 $A$ 的长度
空间复杂度： $O(n)$ ，用于存储生成的新字符串