小红的回文子串

[题目链接](https://www.nowcoder.com/practice/10121932b5c74142b4e54f2972520c95)

思路

给定一个长度为 $n$ 的字符串 $s$ 和一个正整数 $k$ ，统计 $s$ 中有多少个长度为 $k$ 的连续子串是回文串。

暴力枚举

长度为 $k$ 的连续子串共有 $n - k + 1$ 个，起始下标从 $0$ 到 $n - k$ 。对于每个子串，用双指针从两端向中间逐字符比对，判断是否为回文串。

具体步骤：

枚举起始位置 $i$ ，范围 $[0, n-k]$ ；
对子串 $s[i..i+k-1]$ ，令 $l = 0, r = k - 1$ ，逐步比较 $s[i+l]$ 和 $s[i+r]$ ；
若所有对称位置字符都相同，则计数加 1。

样例演示

输入 $n = 5, k = 3$ ，字符串 abaaa：

$i = 0$ ：子串 aba，a == a，b 是中心 -> 回文
$i = 1$ ：子串 baa，b != a -> 不是回文
$i = 2$ ：子串 aaa，a == a，a 是中心 -> 回文

共 2 个，输出 2。

复杂度分析

时间复杂度： $O(n \cdot k)$ ，共 $n - k + 1$ 个子串，每个子串最多比较 $k/2$ 次。
空间复杂度： $O(1)$ ，只用常数额外空间。

代码

C++
Java
Python3
JavaScript

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i + k <= n; i++) {
        bool ok = true;
        for (int l = 0, r = k - 1; l < r; l++, r--) {
            if (s[i + l] != s[i + r]) {
                ok = false;
                break;
            }
        }
        if (ok) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    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 cnt = 0;
        for (int i = 0; i + k <= n; i++) {
            boolean ok = true;
            for (int l = 0, r = k - 1; l < r; l++, r--) {
                if (s.charAt(i + l) != s.charAt(i + r)) {
                    ok = false;
                    break;
                }
            }
            if (ok) cnt++;
        }
        System.out.println(cnt);
    }
}

n, k = map(int, input().split())
s = input()
cnt = 0
for i in range(n - k + 1):
    t = s[i:i+k]
    if t == t[::-1]:
        cnt += 1
print(cnt)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', function(line) {
    lines.push(line.trim());
    if (lines.length === 2) {
        const [n, k] = lines[0].split(' ').map(Number);
        const s = lines[1];
        let cnt = 0;
        for (let i = 0; i + k <= n; i++) {
            let ok = true;
            for (let l = 0, r = k - 1; l < r; l++, r--) {
                if (s[i + l] !== s[i + r]) {
                    ok = false;
                    break;
                }
            }
            if (ok) cnt++;
        }
        console.log(cnt);
        rl.close();
    }
});