提交记录

#include<bits/stdc++.h>
using namespace std;
long long st;
namespace NYNAMESPACE{;
#define int long long
const int mod1=998244353;
const int mod2=1000000087;
const int mod3=1000000097;
const int base=31;
int fp(int a,int b,int mod){
	if(b==0)return 1;
	int x=fp(a*a%mod,b/2,mod);
	if(b%2)x=x*a%mod;
	return x;
}
struct has{
	int len,hb1,hb2,hb3;
	int ha1,ha2,ha3;
	has(){
		len=ha1=ha2=ha3=0;
		hb1=hb2=hb3=1;
	}
	void init(string p){
		len=p.length();
		ha1=ha2=ha3=0;
		//int u=1;
		for(int i=0;i<len;i++){
			int g=p[i]-'a'+1;
			ha1=(ha1*base+g)%mod1;
			ha2=(ha2*base+g)%mod2;
			ha3=(ha3*base+g)%mod3;
			hb1=(hb1*base)%mod1; 
			hb2=(hb2*base)%mod2; 
			hb3=(hb3*base)%mod3; 
		}
	}
}w[200005];
set<pair<int,pair<int,pair<int,int>>>>z;
has pj(has a,has b){
	has c;
	c.len=a.len+b.len;
	c.ha1=(a.ha1*b.hb1%mod1+b.ha1)%mod1;
	c.ha2=(a.ha2*b.hb2%mod1+b.ha2)%mod2;
	c.ha3=(a.ha3*b.hb3%mod1+b.ha3)%mod3;
	c.hb1=a.hb1*b.hb1%mod1;
	c.hb2=a.hb2*b.hb2%mod2;
	c.hb3=a.hb3*b.hb3%mod3;
	return c;
}
int main(){
	z.insert({0,{0,{0,0}}});
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		string k;
		cin>>k;
		w[i].init(k);
	}
	for(int i=1;i<=n;i++){
		int l=0,r=n+10;
		while(l+1<r){
			has p,q=w[i];
			int mid=(l+r)>>1;
			int u=mid;
			while(u){
				if(u&1)p=pj(p,q);
				q=pj(q,q);
				u>>=1;
			}
		//	cout<<i<<' '<<mid<<' '<<p.len<<' '<<p.ha1<<' '<<p.ha2<<endl;
			if(z.find({p.len,{p.ha1,{p.ha2,p.ha3}}})==z.end())r=mid;
			else l=mid;
		}
		cout<<r<<' ';
		has p,q=w[i];
		while(r){
			if(r&1)p=pj(p,q);
			q=pj(q,q);
			r>>=1;
		}
		z.insert({p.len,{p.ha1,{p.ha2,p.ha3}}});
	}
	return 0;
}
}
long long en;
signed main(){
	return NYNAMESPACE::main();
}

时间复杂度:$O(n \log^2n)$