题目链接

小红的回文子串

题目描述

小红拿到了一个字符串。她想知道，该字符串有多少个长度为 k 的连续子串是回文的？

输入:

  • 第一行输入两个正整数 n 和 k，分别代表字符串长度和子串长度
  • 第二行输入一个长度为 n 的、仅由小写字母组成的字符串

输出:

  • 输出一个整数，表示长度为 k 的回文子串数量

解题思路

这是一个字符串处理问题，可以通过以下步骤解决：

  1. 关键发现：

    • 需要检查所有长度为 k 的连续子串
    • 子串总数为 n-k+1 个
    • 每个子串需要判断是否为回文串

  2. 解题策略：

    • 使用滑动窗口遍历所有长度为 k 的子串
    • 对每个子串判断是否为回文
    • 统计回文子串的数量

  3. 具体步骤：

    • 遍历字符串的每个位置 i (0 到 n-k)
    • 检查从位置 i 开始的长度为 k 的子串
    • 判断该子串是否为回文
    • 累计回文子串的数量

代码

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

// 判断字符串是否为回文
bool isPalindrome(const string& s, int start, int len) {
    int left = start;
    int right = start + len - 1;
    while(left < right) {
        if(s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    
    int ans = 0;
    // 遍历所有长度为k的子串
    for(int i = 0; i <= n - k; i++) {
        if(isPalindrome(s, i, k)) {
            ans++;
        }
    }
    
    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    // 判断字符串是否为回文
    static boolean isPalindrome(String s, int start, int len) {
        int left = start;
        int right = start + len - 1;
        while(left < right) {
            if(s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s = sc.next();
        
        int ans = 0;
        // 遍历所有长度为k的子串
        for(int i = 0; i <= n - k; i++) {
            if(isPalindrome(s, i, k)) {
                ans++;
            }
        }
        
        System.out.println(ans);
    }
}

def is_palindrome(s, start, length):
    left = start
    right = start + length - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

n, k = map(int, input().split())
s = input()

ans = 0
# 遍历所有长度为k的子串
for i in range(n - k + 1):
    if is_palindrome(s, i, k):
        ans += 1

print(ans)

算法及复杂度

  • 算法：滑动窗口 + 回文判断
  • 时间复杂度： - 需要检查 个子串，每个子串需要 时间判断
  • 空间复杂度： - 只需要常数空间存储变量