字符串中的子字符串数

Question

给出长度为n的字符串s。我们必须计算给定字符串的字符s [i]存在的子字符串的数量，其中字符s [i]是元音。

示例：在此字符串“ coding”中，字符“ o”出现在10个子字符串中，字符“ i”出现在12个子字符串中。因此总数为22。

约束：字符串大小最大为10 ^ 5，测试用例的数量最大为10 ^ 2。

注意：字符串可以包含大写或小写字母。

我为此编写了一个c ++程序。但是它给的时限超出了。对于较小的字符串，它运行良好。任何人都可以帮助我解决此类问题的实际和更好的逻辑。它也可以在较大的字符串大小下运行。

我的尝试：

#include <bits/stdc++.h>
 using namespace std;


int main() 
{
int t;
cin >> t;

while (t--)
 {
    int n,i;
    cin >> n;

    string str;
    cin >> str;


    unsigned long long int 
  sum=0,pp;
    for(i=0;i<n;i++)
    {
        if(str[i]=='a' || str[i]=='A' || str[i]=='e' || str[i]=='E' || str[i]=='i' || str[i]=='I' || str[i]=='o' || str[i]=='O' || str[i]=='u' || str[i]=='U')
        {
            pp=(i+1)*(n-i);
            sum=sum+pp;
        }

    }

    cout <<sum << '\n';
}

}

Answer 1

请勿强行使用。进行组合作业。

提示＃1：长度为n的字符串具有n*(n+1)/2子字符串。

提示2：元音将原始字符串划分为一组辅音子字符串。长度为k的辅音子串又会生成k*(k+1)/2子串不应计数。

这应该足以使您前进。