题目描述

难度分:$1300$

输入一个长度$\leq 10^6$的字符串$s$，只包含小写字母v和o。

把$s$中的两个相邻的v视作一个w。

输出有多少个wow子序列。

注意：子序列不一定连续。子序列中的w必须由$s$中的相邻v组成。

输入样例$1$

vvvovvv

输出样例$1$

4

输入样例$2$

vvovooovovvovoovoovvvvovovvvov

输出样例$2$

100

算法

前后缀分解

这样统计三元组类型的题目一般就是枚举中间的元素，本题中就是枚举中间的o可能在哪个位置。对于某个位置的o，将o左右两边的w个数交叉组合用乘法原理乘起来即可。

这需要做一个预处理，$pre[i]$表示前缀$[1,i]$中有多少个w，$suf[i]$表示后缀$[i,n]$中有多少个w，状态转移如下：

1. 如果$s[i]=s[i-1]=$v，则有$pre[i]=pre[i-1]+1$，否则$pre[i]=pre[i-1]$。
2. 同理，如果$s[i]=s[i+1]=$v，则有$suf[i]=suf[i+1]+1$，否则$suf[i]=suf[i+1]$。

预处理出$pre$和$suf$两个数组后，再遍历所有满足$s[i]=$o的位置，计算出$i$的贡献累加到答案上即可。

复杂度分析

时间复杂度

遍历了两次字符串，一次预处理，一次求答案，时间复杂度为$O(n)$。

空间复杂度

除了输入的字符串$s$外，开辟了$pre$和$suf$两个数组，空间消耗与$s$串同规模，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1000010;
int n, pre[N], suf[N];
char s[N];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 2; i <= n; i++) {
        int j = n - i + 1;
        pre[i] = pre[i - 1] + (s[i] == 'v' && s[i - 1] == 'v'? 1: 0);
        suf[j] = suf[j + 1] + (s[j] == 'v' && s[j + 1] == 'v'? 1: 0);
    }
    LL ans = 0;
    for(int i = 3; i <= n - 2; i++) {
        if(s[i] == 'o') {
            ans += (LL)pre[i - 1] * suf[i + 1];
        }
    }
    printf("%lld\n", ans);
    return 0;
}