编程题目分享：oppo系统工程师笔试编程题第三题

/*
oppo系统工程师笔试编程题第三题

题目：
定义一个字符串的权值为包含"oppo"的个数，如"oppoppo"的权值为2，"opoop"的权值为0。
输入一个字符串，输出这个字符串的所有子串的权值的和。

举例：
输入：oppoppo
输出：8
解释：
子串oppo权值为1，但是有2个；oppop权值为1；oppopp的权值为1；oppoppo的权值为2；
ppoppo的权值为1；poppo的权值为1。故权值和为 1+1+1+1+2+1+1=8。

方法1：分别计算子串权值。取出所有的子串，再查找每个子串的"oppo"个数。再对子串权值求和。
在取子串是用到左右指针，在计子串权值时需要遍历，一共三层循环。时间复杂度O(n^3)。
时间超时，通过率为10%

方法2：直接计算字符串权值。对原字符串遍历一次，每次找到"oppo"字符串，就累加该字符串对整体权值的影响。
计算方法为 累加 (左侧数 + 1) * (右侧数 + 1)
注意结果使用 long long 类型，否则可能溢出。
*/

#include<iostream>
using namespace std;

int main() {

	string s;  //输入字符串
	cin >> s;
	int n = s.size();  //字符串长度
	long long res = 0;  //用int存储可能会溢出
	for (int i = 0; i < n; i++) {
		if (s.substr(i, 4) == "oppo") {
			//"oppo"左边有i个数，+1是为了包含自身
			//"oppo"右边有n-i-4个数，+1是为了包含自身，即n-i-4+1 = n-i-3
			int left = i + 1, right = n - i - 3;
			//一个oppo子串对字符串权值的贡献为 l * r
			//res += 1ll * left * right;  //表示大小为1的long long数，是为了把计算过程中的int隐式转换为long long
			res += (long long)left * right;  //在任一int数前用 long long 前缀，也可以转换
		}
	}
	cout << res << endl;  //输出结果
}