这个代码的时间复杂度是?
  • 板块学术版
  • 楼主66xyyd
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/10/14 21:37
  • 上次更新2023/11/2 13:46:59
查看原帖
这个代码的时间复杂度是?
946515
66xyyd楼主2023/10/14 21:37
#include<iostream>
using namespace std;
constexpr long long mod=1e9+7,maxn=5e6+2;
int nxta[maxn],nxtb[maxn];
string s;
int n;
long long ans=0;
int main(){
	ios::sync_with_stdio(false);
	cin >> s;
	n=s.length();
	int lasta=n,lastb=n;
	for(int i=n-1;i>=0;i--){
		nxta[i]=lasta;
		nxtb[i]=lastb;
		if(s[i]=='a'){
			lasta=i;
		} else if(s[i]=='b'){
			lastb=i;
		}
	}
	for(int i=lasta;i<n;i=nxta[i]){
		for(int j=nxtb[i];j<n && j!=0;j=nxtb[j]){
			for(int k=nxtb[j];k<n && k!=0;k=nxtb[k]){
				for(int l=nxta[k];l<n && l!=0;l=nxta[l]){
					ans+=(i+1)*(n-l)%mod;
					ans%=mod;
				}
			}
		}
	}
	cout << ans;
	return 0;
}

好像不是 O(∣s∣4)O(|s|^4) 的。

2023/10/14 21:37
加载中...