题解：P9873 [EC Final 2021] Beautiful String

· · 题解

P9873 [EC Final 2021] Beautiful String 题解

博客园链接：P9873 [EC Final 2021] Beautiful String 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

字符串，LCP，Hash，KMP。

分析

首先我们知道 A,B,C,D,E,F 六个非空子串中，A=B=E,C=F，那么 BC=EF，我们设 G=BC=EF，那么原串可以表示为 AGDG。

考虑以某种方法求出 GDG 的方案，再以某种方法用 A 与 G 的关联来统计答案。

法 1：LCP

考虑设 sum_{i,j} 表示 GDG 的左端点在 i，其中 G 的长度 >j 的方案数，那么这个很好求，在 O(n^2) 求 LCP 的时候顺便求出。

设 LCP_{i,j} 表示 LCP(S_i,S_j)，其中 S_i 表示 S 从第 i 个字符开始的后缀，那么 O(n^2) 可以求出，然后搭配 |G|<j-i 的限制，我们就可以统计 sum。

最后考虑用 A 来统计总的答案，其实也就是在求 LCP 的过程中求出。

法 2：Hash + KMP

我们还是像上述过程一样求 sum_{i,j} 表示 GDG 的左端点在 i，其中 G 的长度 >j 的方案数。不过由于没有了 LCP 的辅助，我们 A 与 G 的相同长度关系要用 Hash 求。

考虑新定义 KMP，我们先求出最原始的 next 数组（失配指针），然后我们再重新来一遍，求 Nxt 表示满足长度小于 \frac{1}{2} 现在长度的最长 border，那么只要把更新的数组换掉，再加入长度限制即可解决。

其余统计较为简单。

代码

法 1：LCP

这种方法常数较小。

constexpr int N(5e3+10);

char S[N];
int Cas,n;
int lcp[N],s[N];
int sum[N][N];
ll ans;

int Cmain() {
    scanf("%s",S),n=strlen(S),ans=0;
    DOR(i,n-1,0) {
        FOR(j,0,n)s[j]=0;
        FOR(j,0,n)sum[i][j]=0;
        FOR(j,i+1,n-1) {
            if(S[i]==S[j]) {
                lcp[j]=(j+1<n?lcp[j+1]+1:1);
                if(i+lcp[j]>=j)ans+=sum[j][j-i];
                int r(min(j-i-1,lcp[j]));
                sum[i][0]+=r,--s[0],++s[r];
            } else lcp[j]=0;
        }
        FOR(j,1,((n-i-1)>>1)-1)sum[i][j]+=sum[i][j-1]+s[j-1],s[j]+=s[j-1];
    }
    O(ans,'\n');
    return 0;
}

signed main() {
#ifdef Plus_Cat
    freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
    for((Cas=1); Cas; --Cas)Cmain();
    return 0;
}

法 2：Hash + KMP

constexpr int N(5e3+10),B1(131),P1(1e9+7),B2(13331);
constexpr Piu B(B1,B2);

char s[N];
int Cas,n;
int nxt[N],Nxt[N];
ll ans;
ll cnt[N];
/*Hash*/
Piu pw[N],h[N];

Piu operator -(Piu A,Piu B) {
    return Piu(A.Fi-B.Fi<0?A.Fi-B.Fi+P1:A.Fi-B.Fi,A.Se-B.Se);
}

Piu operator +(Piu A,Piu B) {
    return Piu(A.Fi+B.Fi>=P1?A.Fi+B.Fi-P1:A.Fi+B.Fi,A.Se+B.Se);
}

Piu operator *(Piu A,Piu B) {
    return Piu((ll)A.Fi*B.Fi%P1,A.Se*B.Se);
}

Piu Q(int l,int r) {
    return h[r]-h[l-1]*pw[r-l+1];
}

void Init() {
    pw[0]=Piu(1,1);
    FOR(i,1,n)pw[i]=pw[i-1]*B;
    FOR(i,1,n)h[i]=h[i-1]*B+Piu(s[i],s[i]);
}
/*Solve*/
void Solve(int S) {
    auto len=[&](int i) { return i-S+1; };
    /*DE("nxt");*/
    int it(nxt[S-1]=S-2);
    FOR(i,S,n) {
        while(it>=S-1&&s[i]!=s[it+1])it=nxt[it];
        nxt[i]=++it;
    }
    /*DE("Nxt");*/
    it=Nxt[S-1]=S-2;
    FOR(i,S,n) {
        while(it>=S-1&&(s[i]!=s[it+1]||len(it+1)*2>=len(i)))it=nxt[it];
        Nxt[i]=++it;
    }
    /*DE("Count");*/
    FOR(i,0,len(n))cnt[i]=0;
    FOR(i,S,n)++cnt[len(Nxt[i])];
    DOR(i,n,S)cnt[len(nxt[i])]+=cnt[len(i)];
    DOR(i,len(n)-1,0)cnt[i]+=cnt[i+1];
    FOR(i,1,min(S-1,n-S+1))if(Q(S-i,S-1)==Q(S,S+i-1))ans+=cnt[i+1];
}

int Cmain() {
    scanf("%s",s+1),n=strlen(s+1),Init(),ans=0;
    FOR(i,2,n)Solve(i);
    O(ans,'\n');
    return 0;
}
/*Main*/
signed main() {
#ifdef Plus_Cat
    freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
    for((Cas=1); Cas; --Cas)Cmain();
    return 0;
}