Retucl's blog

By Retucl, history, 4 months ago, In English

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|)$$$.

 
 
 
 
  • Vote: I like it
  • +21
  • Vote: I do not like it