Namomo Test Round 2

题目链接

tag

字符串，思维

solution

对于任意一个长度大于6的namomo串，易证得该字符串的以奇数下标为串首的长度为(6, 8,10 ...len-2)子串都为namomo串(下标从1开始),且长度为(len - k)((k)为偶数， (len-k geq 6))的namomo串分别有(k+1)个

所以我们可以遍历字符串找到以(i)为下标长度为6的满足条件的namomo串，然后不断向后找两个字符，判断是否可以和前面的字符串连接之后是否仍是namomo串，直至不满足为止，得到以(i)开头的最长namomo串，此串对答案的贡献就是(frac{(len/ 2 - 2)* (len / 2 - 2 + 1)}{2})

另外需要注意该串的后两位字符有可能成为下一个满足条件的namomo串的前两位,故我们需要将下标置于(i + len - 3)处

code

//created by pyoxiao on 2020/07/06
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define CL(a, b) memset(a, b, sizeof(a))
using namespace std;
const int mod = 1e9 + 7;
LL fpow(LL a, LL b, LL p = mod){LL ans = 1; a %= p; while(b) {if(b & 1) ans = ans * a % p; b >>= 1; a = a * a % p;} return ans;}
LL gcd(LL a, LL b){return b == 0 ? a : gcd(b, a % b);}
char s[5000010];
char yy[] = {'a', 'e', 'i', 'o', 'u'};
bool check(char s) {
    for(int k = 0; k < 5; k ++) {
        if(s == yy[k]) return true;
    }
    return false;
}
void solve() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    LL ans = 0;
    for(int i = 1; i <= n - 5; i ++) {
        bool flag = 0;
        for(int k = 0; k < 4; k ++) {
            if(k & 1) flag |= (!check(s[i + k]));
            else flag |= check(s[i + k]);
        }
        flag |= (s[i + 2] != s[i + 4]);
        flag |= (s[i + 3] != s[i + 5]);
        if(flag) continue;
        else {
            int pos = i + 6;
            char tmp1 = s[i + 2], tmp2 = s[i + 3];
            while(pos + 1 <= n) {
                if(s[pos] == tmp1 && s[pos + 1] == tmp2) pos += 2;
                else break;
            }
            LL len = pos - i; len /= 2; len -= 2;
            ans += len * (len + 1) / 2;
            i = pos - 3;
        }
    }
    printf("%lld
", ans);
}
int main() {
    int T = 1;
    // scanf("%d", &T);
    while(T --) 
        solve();
    return 0;
}