小红定义一个长度为奇数的字符串的“中值”为中间那个字符。例如"kou"的中值是'o'。现在小红拿到了一个字符串,她想知道某个字符是多少个子串的中值。你能帮帮她吗?

输入格式

第一行输入一个正整数n和一个英文小写字符chr。代表字符串长度和询问的字符。第二行输入一个长度为n的、仅由小写字母组成的字符串。$1 \leq n \leq 10^5$

输出格式

一个整数,代表中值为chr的连续子串数量。

输入样例:

4 b
abcb

输出样例:

3

说明: 有两个"b"字符串和一个"abc"字符串的中值都是'b'。


题目分析

简单思维题, 找到中点后双指针向两边移动即可。

由于(对于中点 c):

aaccc

这种也算合法字符串(作为中点的字符可以出现多次),所以我们不需要双指针模拟,找到最短半径即可,答案为: $$ min(i, n - i + 1) $$

代码实现

#include <iostream>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;

int n;
LL cnt;
char ch, s[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> ch >> s + 1;
    for(int i = 1; i <= n; ++i)
        if(s[i] == ch)
            cnt += min(i, n - i + 1);
    cout << cnt;
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status