奶牛碑文

约翰和他的奶牛在大草原漫游，在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言，只包括三个大写字母 C,O,W。

尽管约翰看不懂，但是令他高兴的是，C,O,W的顺序形式构成了一句他最喜欢的奶牛单词 “COW”。

现在，他想知道有多少次 COW出现在文本中。

如果 COW内穿插了其他字符，只要COW字符出现在正确的顺序，约翰也不介意。

他也不介意出现不同的COW共享一些字母。例如CWOW出现了1次COW，CCOW算出现了2次COW，CCOOWW算出现了8次COW。

输入：

第一行一个整数 N。（1≤N≤105）

第二行为含有 N 个字符的字符串，字符只可能是 C,O,W。

输出：

输出 COW 作为输入字符串的子串出现的次数（不一定是连续的），答案可能会很大。

样例：

1
2
6
COOWWW
1
6

参考代码

  1. 暴力法：三重for循环分别对C,O,W进行遍历，可能会导致超时。
  2. 利用前缀和思想：空间复杂度换时间复杂度，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
using namespace std;

char str[100005];
int numc[100005], numw[100005], n;
long long ans;

int main() {
	cin >> n >> str;
	for (int i = 0; str[i]; ++i) {//从前向后遍历 计算有多少个C（前缀和C）
		if (i == 0) {
			numc[i] = (str[i] == 'C');
		} else {
			numc[i] = numc[i - 1] + (str[i] == 'C');
		}
	}
	for (int i = n - 1; i >= 0; --i) {//从后向前遍历 计算有多少个W（后缀和W）
		if (i == n - 1) {
			numw[i] = (str[i] == 'W');
		} else {
			numw[i] = numw[i + 1] + (str[i] == 'W');
		}
	}
	for (int i = 0; str[i]; ++i) {//计算经过第i个O时的答案
		if (str[i] == 'O') ans += (long long)numc[i] * numw[i];
	}
	cout << ans << endl;
	return 0;
}