Solução por Leonardo Paes
Para resolver este problema, utilizaremos as ideias de: Soma de Prefixos e Soma de Sufixos.
Utilizaremos as técnicas acima para contar a quantidade de 'w's que ocorrem no prefixo e sufixo de cada posição da string 
.
Tendo isso calculado, para obtermos a resposta final do problema, basta, para cada ocorrência do caractere 'o' na string , somarmos na variável ![resposta = prefixo[i] \cdot sufixo[i]](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_b3557463b8ac4d857f1a7080f3f5a2ed.gif?w=640&ssl=1)
. (Pelo princípio multiplicativo).
Segue abaixo o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 1e6+100; | |
| long long prefixo[maxn], sufixo[maxn]; | |
| int main(){ | |
| string s; | |
| cin >> s; | |
| long long resposta = 0; | |
| for(int i=1; i<s.size(); i++){ // Precalcular quantidade de 'w's no meu prefixo. | |
| prefixo[i]=prefixo[i-1]; | |
| if(s[i]=='v' and s[i-1]=='v'){ | |
| prefixo[i]++; | |
| } | |
| } | |
| for(int i=s.size()-2; i>=0; i--){ // Precalcular quantidade de 'w's no meu sufixo. | |
| sufixo[i]=sufixo[i+1]; | |
| if(s[i]=='v' and s[i+1]=='v'){ | |
| sufixo[i]++; | |
| } | |
| } | |
| for(int i=0; i<s.size(); i++){ // Calcular a resposta. | |
| if(s[i]=='o'){ | |
| resposta += (sufixo[i])*(prefixo[i]); | |
| } | |
| } | |
| cout << resposta << endl; | |
| return 0; | |
| } | |