B.Namomo子串(模拟&DP)

思路：简单模拟&$dp$。

显然我们只需每次找到$namomo$类型的串，然后枚举循环次数。

假设从长度为9开始(前两个$mo$不计算)$mo$的个数$x$个，显然$na$开头的贡献数为$x+1$个（分别是长度为$6，8\dots$）。

接下来不以$na$开头的子串显然有$1+2+\dots x$个。

因为长度为$6$的有$x$个，$8$的有$x-1$个，长度为$2x+4$有一个。

综上$ans+=(x+1+\dfrac{(x+1)x}{2})$

实现的话可以顺序模拟，或者$dp$后再倒着计算。

注意有一个$WA$点是：

$ep: namomovuvu$ ，这样的串$namomo,movuvu$都是。所以每次遍历完一个$namomo$串后，下标$i$应该置为最后一个$mo$的$m$，而不能变成$vu$的$v$。

$dp写法$：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
char a[N];
char c[5]={'a','e','i','o','u'};
bool vis[N];
ll dp[N][2]; 
int main(){scanf("%s",a+1);	int n=strlen(a+1);for(int i=1;i<=n;i++){int f=0;for(int j=0;j<5;j++){if(c[j]==a[i]){f=1;vis[i]=1;break;}}if(!f){if(i>2&&a[i-2]==a[i]) dp[i][0]=max(dp[i-2][0]+1,1LL);else dp[i][0]=1;}else {if(i>2&&a[i-2]==a[i]) dp[i][1]=max(dp[i-2][1]+1,1LL);else dp[i][1]=1;}}ll ans=0;for(int i=n;i>=6;i--){if(vis[i]&&!vis[i-1]){if(dp[i][1]<2||dp[i-1][0]<2) continue;ll x=min(dp[i][1],dp[i-1][0]);int len=x*2;int st=i-1-len;int f=0; if(st<1) st+=2,f=1;if(!f&&!vis[st]&&vis[st+1]){ans+=(x-1)+(x-2)*(x-1)/2; }else ans+=(x-2)*(x-1)/2;i=st+2; } }printf("%lld\n",ans);return 0;
}

顺序模拟：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
char a[N];
char c[5]={'a','e','i','o','u'};
bool check(int i){for(int j=0;j<5;j++) if(c[j]==a[i]) return 1;return 0;
}
bool namo(int i){if(!check(i)&&check(i+1)&&check(i+3)&&!check(i+2)&&a[i+2]==a[i+4]&&a[i+3]==a[i+5]) return 1;return 0;
} 
int main(){scanf("%s",a+1);	int n=strlen(a+1);ll ans=0;for(int i=1;i+5<=n;i++){if(namo(i)){int j=i+6,k=j+1;while(k<=n&&a[j]==a[i+2]&&a[k]==a[i+3]) j+=2,k+=2;int len=k-2-i+1;ll cnt=(len-6)/2;ans+=cnt+(cnt+1)*cnt/2+1;i=j-2-1;}}printf("%lld\n",ans);return 0;
}