### Retucl's blog

By Retucl, history, 4 months ago,

I solved 1621I - Two Sequences in this way but a bit different.

I calculated the maximum number of copies of the minimum suffix of each prefix of a string in a simple way:

int A[N];

bool cmp(int l1,int r1,int l2,int r2){
if(r1-l1!=r2-l2) return false;
for(int i=0;i<=r1-l1;++i)
if(A[l1+i]!=A[l2+i]) return false;
return true;
}

// mSuf1[i] means that A[mSuf1[i]:i] is the minimum suffix of A[1:i]
// mSuf2[i] means that A[mSuf2[i]:i] is the maximum number of copies of the minimum suffix of A[1:i]

for(int t=L;t<=R;++t){
mSuf2[t]=mSuf1[t];
if(cmp(mSuf1[mSuf1[t]-1],mSuf1[t]-1,mSuf1[t],t))
mSuf2[t]=mSuf2[mSuf1[t]-1];
}

// The loop above looks so slow but it was accepted.


My submission: 143043686.

So I wanna know the upper bound of the time complexity of this loop and how to construct the string to get this bound. The size of the character set can be $O(|S|)$.

• +21