HDU7015 Another String

Another String

Sol

考虑预处理 F[i][j] 表示以下标 i 为左端点的字符串和以下标 j 为左端点的字符串 , 在满足 k 匹配的条件下 , 最长能匹配 F[i][j] 的长度

也就是 S[i+L-1] 与 S[j+L-1] 满足 K 匹配 , 这个 L 是最大的 , 且两个串不相交

(还要满足 j+L-1 \leq n 且 i+L-1 )

利用双指针预处理 O(n^2)

for(int st=2;st<=n;++st){
            int diff = 0 ,L = 0 ;//, p = st;
            for(int q=1,p=st;q<=n;++q,++p){
                while(q+L<p&&p+L<=n&&(diff<k||diff<=k&&s[q+L]==s[p+L])){
                    diff+=s[q+L]!=s[p+L];
                    L++;
                }
                f[q][p] = L;
                diff-=s[q]!=s[p];
                L--;
            }
        }

考虑我们要统计的答案是

\sum_{i=1}^{t-1}\sum_{j=t}^nF[i][j]

里面的式子就表示, t 状态下, 两个匹配串以 i,j 为左端点,有 F[i][j] 个串可以 k 匹配

现在要求快速统计这个式子.

然后考虑 t 将字符串 S , 分割为 A[1…t-1] 和 B[t…n] ( 2\leq t\leq n )

考虑 A 中的一个子串 s[i,j] 与 B 的一个子串 t[p,q] 匹配

显然当 j\leq t-1 且 t\leq p 时 ,这两个子串会一直处于匹配状态

也就是说当 t 递减时 , 对一对满足 k 匹配的 (s[i,j] ,t[p,q]) 串来说 ,

t 递减到 p 时 , 会开始对答案有贡献 ; t 递减到 j 时 , 就不再对答案有贡献了

然后我们考虑按照 t 递减的顺序计算答案

当 t \to t-1 时 , 看看答案发生了什么改变 :

① 要删去原本 A 串中以 t-1 为右端点和 B 串中以 [t,n] 中的点为左端点 k 匹配的贡献

② 要加上 A 串中 以[1,t-2] 为左端点 与 B 串中以 t 为左端点的子串的 k 匹配贡献

理解了这个 , 看官方题解即可

#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
char s[N];
int mx[N],f[N][N],k,n,T,cnt[N][N],ANS[N];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        scanf(" %s",s+1);
        for(int st=2;st<=n;++st){
            int diff = 0 ,L = 0 ;//, p = st;
            for(int q=1,p=st;q<=n;++q,++p){
                while(q+L<p&&p+L<=n&&(diff<k||diff<=k&&s[q+L]==s[p+L])){
                    diff+=s[q+L]!=s[p+L];
                    L++;
                }
                f[q][p] = L;
                diff-=s[q]!=s[p];
                L--;
            }
        }
        for(int i=1;i<=n;++i){
            mx[i] = n/2+1;
            for(int j=1;j<=n;++j)
                cnt[i][j]=0;
        }
        int ans = 0 ;
        for(int t=n;t;--t){
            for(int i=1;i+1<=t;++i){
                while(mx[i]>t-i){
                    ans-=cnt[i][mx[i]];
                    cnt[i][mx[i]-1]+=cnt[i][mx[i]];
                    mx[i]--;
                }
            }
            for(int i=1;i+1<=t;++i){
                int g = f[i][t]; 
                cnt[i][g]++;
                ans+=g;
            }
            ANS[t]=ans;
            if(mx[t-1]>0){
                ans-=cnt[t-1][1];
                mx[t-1]--;
            }
        }
        for(int i=2;i<=n;++i)
            printf("%d\n",ANS[i]);
    }
    return 0;
}