题目描述

难度分:$1300$

输入长度$\leq 10^6$的字符串$s$，只包含小写英文字母。

输出有多少个子串，以heavy开头，并以metal结尾。

输入样例$1$

heavymetalisheavymetal

输出样例$1$

3

输入样例$2$

heavymetalismetal

输出样例$2$

2

输入样例$3$

trueheavymetalissotruewellitisalsosoheavythatyoucanalmostfeeltheweightofmetalonyou

输出样例$3$

3

算法

枚举+二分查找

能写二分我就不会写双指针，我们可以先遍历$s$串，分别将heavy和metal的出现位置存入$pos_1$和$pos_2$两个位置数组中，本题给定的前后缀比较短，可以直接暴力，如果很长的话就需要用字符串哈希或者$kmp$。

然后遍历$pos_1$的每个位置$x$，以$x$开头的子串如果要以某个metal结尾，那这个metal的出现位置就至少要是$x+5$，因此可以二分查找$pos_2$数组，找到第一个符合条件的位置$j$。$j$开始一直到$pos_2$的最后一个位置都可以和$x$组成heavy开头metal结尾的子串，$pos_2.size()-j$就是$x$能够贡献的子串数目。

复杂度分析

时间复杂度

预处理出$pos_1$和$pos_2$两个位置数组，时间复杂度为$O(n)$。接下来遍历$pos_1$中的每个位置$x$，找到符合题意的$pos_2$中的位置，每个$x$要对$pos_2$进行一次二分查找，而$pos_1$和$pos_2$的规模在最差情况下都是$O(n)$的，所以二分查找的时间复杂度为$O(log_2n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

两个位置数组$pos_1$和$pos_2$，都是线性空间，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1000010;
char s[N];
int n;

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    vector<int> pos1, pos2;
    for(int i = 1; i + 4 <= n; i++) {
        if(s[i] == 'h' && s[i + 1] == 'e' && s[i + 2] == 'a' && s[i + 3] == 'v' && s[i + 4] == 'y') {
            pos1.push_back(i);
        }
        if(s[i] == 'm' && s[i + 1] == 'e' && s[i + 2] == 't' && s[i + 3] == 'a' && s[i + 4] == 'l') {
            pos2.push_back(i);
        }
    }
    long long ans = 0;
    for(int x: pos1) {
        ans += pos2.end() - lower_bound(pos2.begin(), pos2.end(), x + 5);
    }
    printf("%lld\n", ans);
    return 0;
}