B.Namomo 하위 문자열(아날로그 &DP)

사고방식: 단순 시뮬레이션 & dpdpdp.
분명히 우리는 매번 n a m o m o namomo namomo 형식의 열을 찾은 다음에 순환 횟수를 매거할 수 있다.
가령 길이가 9부터 시작한다고 가정하면 (전 두 개의 momo는 계산하지 않는다) momo의 개수 xxxx개, 분명히 nana가 시작하는 공헌수는 x+1x+1x+1개(각각 길이는 6, 8...6, 8\dots 6, 8...)이다.
다음 n a na 로 시작하지 않는 하위 문자열에는 분명히 1 + 2 +... x 1 + 2 +\dots x 1 + 2 +... x 가 있습니다.
길이가 66인 것은 xx개, 88인 것은 x-3-1x-3개, 길이가 2x+42x+4 2x+4 2x+4 하나이기 때문이다.
종합 a n s + = (x + 1 + (x + 1) x 2)ans + = (x+1 +\dfrac {(x+1) x} {2}) ans + = (x+1+2(x+1) x)
실현되면 순서대로 시뮬레이션하거나 dpdpdp 후 거꾸로 계산할 수 있습니다.
WA WA 점은 다음과 같습니다.
p:n a m o m o v u v ep:namomovuvu ep:namomovuvu, 이런 열 na m o m o, m o v u namomomo, movuvu namomo, movuvu 모두 입니다.그래서 매번 na m o m o namomo namomo 열을 반복한 후, 아래 표기 ii는 마지막 m o mo의 m m m로 설정해야 하며, v u vu vu의 v v가 될 수 없습니다.
d p 쓰기 dp 쓰기 dp 쓰기:

#include
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
#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
",ans);
	return 0;
}

순차 시뮬레이션:

#include
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
#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
",ans);
	return 0;
}