P7114

Aryper · 2021-11-14 13:16:06 · 个人记录

[NOIP2020] 字符串匹配

不会扩展 KMP 怎么办？没关系，我们还是有可观的暴力分数的。

这里计数的最大难点在于循环节的寻找（需要用到扩展 KMP 才能较为优美的搞出来，当然还有使用 Hash 也可以搞出来）。

我们引入 Z 函数 z(i)。

然后循环节的数量可以这样找：

前缀 A 为 [0,i]，那么 z(i+1) 会与前缀有重合，重合的部分显然就是一个循环，如果与前缀重合的长度还超过了 A 那说明有多个循环节。于是乎，以 A 为单位的循环数目为 \lfloor\dfrac{z(i+1)}{i+1}\rfloor+1。

然后就是愉快地分奇偶计数。

我们扫描前缀，得到前缀的所有可能的 F(A)，并将其统计入树状数组。

现在找到的循环节要求 B 不为空，因此先利用前面的统计来计算答案。

显然，循环节的奇偶数与答案统计有着莫大的关系。

如果说，我们的节数是奇数的话，发现不论节数如何变化，后缀 C 的 F(C) 始终不变（因为每次跳到下一个奇数节数的地方相当于加上 2 个循环节，那相同的字母加上了偶数次，就对 C 的 F(C) 没有影响了）。因此我们的 F(A) 只要满足 F(A)\le F(s[i+1,n-1]) 就可以了。不需要再动态地去计算 F(C) 了。

如果说节数是偶数的话，类比奇数的情况，我们发现这个 F(C)=F(s)，因为一开始的前缀 A 就对 F(C) 没有影响。因此统计一下 F(A)\le F(s) 就好了。

节数是奇数的个数显然是循环节数除以 2 上取整，偶数的个数就是节数除以 2 下取整。

然后就完了。

时间复杂度 O(Tn)。（\log 26 可以视作小常数）

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

const ll N=(1<<20);

ll T,n,pre,suf,all,ans;

ll z[N+5],bef[30],aft[30],c[30];

char s[N+5];

void add(ll x) {
    for(;x<=27;x+=x&-x) c[x]++;
}

ll ask(ll x) {
    ll res=0;for(;x;x-=x&-x) res+=c[x];return res;
}

void getZ() {
    z[0]=n;
    ll now=0;
    while(now+1<n&&s[now]==s[now+1]) now++;
    z[1]=now;
    ll p0=1;
    for(ll i=2;i<n;i++) {
        if(i+z[i-p0]<p0+z[p0]) {
            z[i]=z[i-p0];
        }
        else {
            now=p0+z[p0]-i;
            now=max(now,0ll);
            while(now+i<n&&s[now]==s[now+i]) now++;
            z[i]=now;p0=i;
        }
    }
}

void init() {
    memset(aft,0,sizeof(aft));
    memset(bef,0,sizeof(bef));
    memset(c,0,sizeof(c));
    all=pre=suf=ans=0;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    T=read();

    while(T--) {
        scanf("%s",s);
        n=strlen(s);
        init();
        getZ();
        for(ll i=0;i<n;i++) {
            if(i+z[i]==n) z[i]--;
        }
        for(ll i=0;i<n;i++) aft[s[i]-'a']++;
        for(ll i=0;i<26;i++) {
            if(aft[i]&1) all++;
        }
        suf=all;
        for(ll i=0;i<n;i++) {
            if(aft[s[i]-'a']&1) suf--;
            else suf++;
            aft[s[i]-'a']--;
            if(bef[s[i]-'a']&1) pre--;
            else pre++;
            bef[s[i]-'a']++;
            if(i!=0&&i!=n-1) {
                ll tmp=z[i+1]/(i+1)+1;
                ans+=tmp/2*ask(all+1)+(tmp-tmp/2)*ask(suf+1);
            }
            add(pre+1);
        }
        writeln(ans);
    }

    return 0;
}