题解 P7114 【字符串匹配（洛谷民间数据）】

· · 题解

严格 O(n) 的解法出来了。

首先，我们必须知道一个事实：

如果一个长度为 n 的字符串有长度为 m 的循环节，那么，其前 n-m 位与后 n-m 位相同是充分必要条件。

具体可以通过看一张图直观理解：

然后，我们考虑Z算法（即【模板】扩展 KMP（Z 函数））。

对于位置 i，其 Z 数组 Z_i 的定义是从位置 i 起始的后缀与整个串的LCP长度。具体应该怎样求出可以参照该题题解，此处不讲述。

回到本题。我们考虑枚举 AB 串的长度 i，并计算有多少前缀可以被表示成 (AB)^k 的形式。明显此前缀的长度必然为 ik 。

则依据我们刚才的循环节理论，假如其可以被表示成 (AB)^k 形式，必有 s_{[i,ik-1]}=s_{[0,i(k-1)-1]}，其中 s_{[a,b]} 表示原串从 a 到 b 的子串，下标自 0 开始。即，从 i 开始长度为 i(k-1) 的子串，必定等于长度为 i(k-1) 的前缀。

考虑 s_{[i,ik-1]} 即为原串中自第 i 位起始的后缀的前缀；则如果有 ik-i\leq Z_i，即该前缀的长度不大于 Z_i 的大小，则依据 Z 数组的意义，有 s_{[i,ik-1]}=s_{[0,i(k-1)-1]}（因为 Z 表示的是公共前缀的长度）。

于是，只有 ik-i\leq Z_i 的长度为 ik 的前缀 (AB)^k，才有长度为 i 的循环节 AB。上式可以被等价表述为 k\leq\dfrac{Z_i}{i}+1，即对于一个位置 i，共有 \dfrac{Z_i}{i}+1 个合法的 k。当然，合法的 k，其后缀必然不为空，这意味着 Z_i 应与 n-i-1 取 \min。

在下文中，定义“奇偶性”为某个串中出现奇数次的字符数量。

考虑截去长度为 ik 的前缀后剩下的后缀，则该后缀则为 C。明显，当 k 是奇数和 k 是偶数时，C 的奇偶性只有两种可能。

更准确地说，k 是奇数时，有其奇偶性全部等价于起始于 i 的后缀的奇偶性；k 是偶数时，其奇偶性全部等价于起始于 2i 的后缀的奇偶性；但是因为 2i 本身相当于 i 出现两次，出现两次的串的奇偶性必为 0，故其实际上就相当于整个串的奇偶性。

于是，我们会发现，共有 \left\lceil\dfrac{\dfrac{Z_i}{i}+1}{2}\right\rceil 个后缀是和 i 开头的后缀同奇偶的，共有 \left\lfloor\dfrac{\dfrac{Z_i}{i}+1}{2}\right\rfloor 个后缀是和整个串同奇偶的（分别对应着 k 为奇和 k 为偶两种情形）。

我们下面考虑有多少个合法的 A 串。明显它必须是 AB 串的某个前缀，也即整个串的前缀。

于是，我们要考虑的，就是 i 之前的前缀中，共有多少个的奇偶性不大于 i 开头的后缀的奇偶性，即 k 为奇数时合法 A 的数量；共有多少个的奇偶性不大于整个串的奇偶性，即 k 为偶数时合法 A 的数量；然后此为奇为偶时的 A 的数量，再分别乘上我们刚才求出的为奇为偶时的 C 的数量，就是 AB 长度为 i 的合法拆分的数量。

我们可以先考虑使用桶进行维护所有前缀中各奇偶性的出现次数，每次暴力扫过桶处理。则目前的复杂度是 O(26n) 的。

先贴出考场代码（会TLE）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,Z[2001000],mas[2001000],sum[30],CN,BN;
ll res;
char s[2001000];
int COUNT(int ip){
    int ret=0;
    while(ip)ret+=ip&1,ip>>=1;
    return ret;
}
int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        scanf("%s",s),n=strlen(s),memset(sum,0,sizeof(sum)),res=CN=BN=0;
        mas[0]=1<<(s[0]-'a');
        for(int i=1;i<n;i++)mas[i]=mas[i-1]^(1<<(s[i]-'a'));
        CN=COUNT(mas[n-1]);
        int Centre=-1,Rpos=-1;
        for(int i=1;i<n;i++){
            if(i<=Rpos)Z[i]=min(Z[i-Centre],Rpos-i+1);
            else Z[i]=0;
            while(i+Z[i]<n&&s[Z[i]]==s[i+Z[i]])Z[i]++;
            if(i+Z[i]>Rpos)Centre=i,Rpos=i+Z[i]-1;
        }
//      for(int i=1;i<n;i++)printf("%d ",Z[i]);puts("");
        for(int i=1;i<n;i++){
            int C1=mas[n-1]^mas[i-1];
            C1=COUNT(C1);
            int tot=min(Z[i],n-i-1)/i+1;
            int N1=(tot+1)>>1,N2=(tot)>>1;
//          printf("%d:%d %d\n",tot,N1,N2);
            for(int j=0;j<=C1;j++)res+=1ll*sum[j]*N1;
            sum[COUNT(mas[i-1])]++;
            res+=1ll*BN*N2;
            if(COUNT(mas[i-1])<=CN)BN++;
        }
        printf("%lld\n",res);
    }
    return 0;
}

下面考虑优化。

首先，上述程序统计奇偶性时，是使用了一个状压来统计——但这本身就有一个 26 的常数。换成桶来统计，即可做到 O(n) 来处理。

然后，观察到随着 i 每次增加 1，长度为 i 的后缀的奇偶性最多只会变化 1。这意味着我们可以直接在前一位统计的基础上，直接加上或减去有所变动的那一个桶里的值即可。

这两个优化加上，即可把复杂度优化到严格 O(n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,Z[2001000],cnt1[30],cnt2[30],sum[30],CN,BN,nown,sumn,nown2;
ll res;
char s[2001000];
int main(){
//  freopen("string.in","r",stdin);
//  freopen("string.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        scanf("%s",s),n=strlen(s),memset(sum,0,sizeof(sum)),memset(cnt1,0,sizeof(cnt1)),memset(cnt2,0,sizeof(cnt2)),res=CN=BN=0;
        for(int i=0;i<n;i++)cnt1[s[i]-'a']^=1;
        for(int i=0;i<26;i++)CN+=cnt1[i];
        int Centre=-1,Rpos=-1;
        for(int i=1;i<n;i++){
            if(i<=Rpos)Z[i]=min(Z[i-Centre],Rpos-i+1);
            else Z[i]=0;
            while(i+Z[i]<n&&s[Z[i]]==s[i+Z[i]])Z[i]++;
            if(i+Z[i]>Rpos)Centre=i,Rpos=i+Z[i]-1;
        }
//      for(int i=1;i<n;i++)printf("%d ",Z[i]);puts("");
        nown=CN,nown2=sumn=0;
        for(int i=1;i<n;i++){
            if(cnt1[s[i-1]-'a'])sumn-=sum[nown--];
            else sumn+=sum[++nown];
            cnt1[s[i-1]-'a']^=1;
            int tot=min(Z[i],n-i-1)/i+1;
            int N1=(tot+1)>>1,N2=(tot)>>1;
//          printf("%d:%d %d\n",tot,N1,N2);
            res+=1ll*sumn*N1;
            if(cnt2[s[i-1]-'a'])nown2--;
            else nown2++;
            cnt2[s[i-1]-'a']^=1;
            sum[nown2]++;
            if(nown2<=nown)sumn++;
            res+=1ll*BN*N2;
            if(nown2<=CN)BN++;
        }
        printf("%lld\n",res);
    }
    return 0;
}