目录

1.问题描述

2.问题求解

---

 1.问题描述 描述

在庆祝祖国母亲70华诞之际，老师给小乐乐出了一个问题。大家都知道China的英文缩写是CHN，那么给你一个字符串s，你需要做的是统计s中子串“CHN”的个数。

子串的定义：存在任意下标a < b < c，那么“s[a]s[b]s[c]”就构成s的一个子串。如“ABC”的子串有“A”、“B”、“C”、“AB”、“AC”、“BC”、“ABC”。

输入描述：

输入只包含大写字母的字符串s。(1 ≤ length ≤ 8000)

输出描述：

输出一个整数，为字符串s中字串“CHN”的数量。

题目链接小乐乐与字符串_牛客题霸_牛客网 (nowcoder.com)

2.问题求解

我们拿到题目第一反应想到的就是三个for循环暴力求解

#include
int main()
{
    char s[8000] = { 0 };
    gets(s);
    int i = strlen(s);
    int a = 0;
    int b = 0;
    int c = 0;
    long long count = 0;
    for (a = 0; a < i - 2; a++)
    {
        if (s[a] == 'C')
        {
            for (b = a + 1; b < i - 1; b++)
            {
                if (s[b] == 'H')
                {
                    for (c = b + 1; c < i; c++)
                    {
                        if (s[c] == 'N')
                            count++;
                    }
                }
            }
        }
    }
    printf("%ld", count);
    return 0;
}

但是这里的字符串长度为8e3，于是我们暴力求解后便得到了它

 我们为了算法简洁，我们想到这样一个办法，先遍历字符串，我们设定‘C’的数量为c，当我们遇到一个‘C’时，c++，当又遇到‘H’时我们以此时的下标向后进行一个for循环，碰到一个‘N’则有一个‘’CHN‘’字串。这样的方法就可以减少一次for循环，有效避免了超时的问题。

#include
int main()
{
    char s[8000] = { 0 };
    gets(s);
    int i = strlen(s);
    int a = 0;
    int b = 0;
    int c = 0;
    long long count = 0;
    for (a = 0; a < i; a++)
    {
        if (s[a] == 'C')
            b++;
        if (s[a] == 'H')
        {
            for (c = a + 1; c < i; c++)
            {
                if (s[c] == 'N')
                    count += b;
            }
        }

    }
    printf("%ld", count);
    return 0;
}

本文到此为止，感谢大家的阅读，欢迎大家点赞评论互关，祝大家万事如意。