CCA的字符串

题目链接：nowcoder 213876

到主站看：https://blog.csdn.net/weixin_43346722/article/details/112134361

题目大意

求在一个字符串中，有多少个子串里包含 NowCoder。

思路

考虑每次找到一个 NowCoder的子串，会多产生多少种方案。

假设你找到的这个子串的最左边是第 个。
左边界的范围是 （ 是上一个 Nowcoder子串最左边的位置），右边界则是从这个子串的最右边到全部。

然后我们把答案加在一起，就可以了。

代码

#include<cstdio>
#include<cstring>
#define ll long long

using namespace std;

int asize, bsize, last;
char a[1000001], b[8] = {'N', 'o', 'w', 'C', 'o', 'd', 'e', 'r'};
bool have;
ll ans;

int main() {
    scanf("%s", a + 1);

    asize = strlen(a + 1);

    for (int i = 8; i <= asize; i++) {
        have = 1;
        for (int j = 0; j < 8; j++)
            if (a[i - j] != b[7 - j]) {
                have = 0;
                break;
            }
        if (have) {
            ans += (ll)(i - 7 - last) * (ll)(asize - i + 1);
            last = i - 7;
        }
    }

    printf("%lld", ans);

    return 0;
}