LOJ#3387「NOIP2020」字符串匹配 题解

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define uint unsigned long long
5
#define SET(a,b) memset(a,b,sizeof(a))
6
#define CPY(a,b) memcpy(a,b,sizeof(b))
7
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
8
#define per(i,j,k) for(int i=(j);i>=(k);--i)
9
int read() {
10
    int a=0, f=1; char c=getchar();
11
    while(!isdigit(c)) {
12
        if(c=='-') f=-1;
13
        c=getchar();
14
    }
15
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
16
    return a*f;
17
}
18
const int N=1048580;
19
const uint P=1610612741;
20
int T, n, ans, c[30], pre[N], suf[N], pos[N];
21
uint h[N], PP[N], f[N][21];
22
char s[N];
23
uint getlr(int l,int r) {
24
    return h[r]-h[l-1]*PP[r-l+1];
25
}
26

27
struct BIT {
28
    int c[N];
29
    void insert(int x,int y) {
30
        ++x;
31
        for(;x<=n+1;x+=x&-x) c[x]+=y;
32
    }
33
    int query(int x) {
34
        int y=0;
35
        ++x;
36
        for(;x;x-=x&-x) y+=c[x];
37
        return y;
38
    }
39
} Tr;
40
void iinit() {
41
    SET(c,0);
42
    pre[1]=1, ++c[s[1]-'a'+1];
43
    h[1]=s[1]-'a'+1;
44
    PP[0]=1, PP[1]=P;
45
    for(int i=2;i<=n;++i) {
46
        h[i]=h[i-1]*P+(s[i]-'a'+1);
47
        PP[i]=PP[i-1]*P;
48
        if(c[s[i]-'a'+1]%2==0) pre[i]=pre[i-1]+1;
49
        else pre[i]=pre[i-1]-1;
50
        ++c[s[i]-'a'+1];
51
    }
52
    SET(c,0);
53
    suf[n]=1, ++c[s[n]-'a'+1];
54
    for(int i=n-1;i;--i) {
55
        if(c[s[i]-'a'+1]%2==0) suf[i]=suf[i+1]+1;
56
        else suf[i]=suf[i+1]-1;
57
        ++c[s[i]-'a'+1];
58
        f[i][0]=h[i];
59
        for(int j=1;i*(1<<j)<=n;++j) {
60
            f[i][j]=f[i][j-1]*(PP[i*(1<<(j-1))]+1);
61
            if(i*(1<<(j+1))>n) pos[i]=j;
62
        }
63
    }
64
}
65
pair<int,int> calc(int i) {
66
    int p=0, q=0, j=pos[i];
67
    for(;~j;--j) {
68
        int t=i*(1<<j);
69
        if(p+t>n) continue;
70
        if(f[i][j]==getlr(p+1,p+t)) p+=t, q|=1<<j;
71
    }
72
    return make_pair(p,q);
73
}
74
void solve() {
75
    ans=0;
76
    scanf("%s",s+1);
77
    n=strlen(s+1);
78
    memset(Tr.c,0,(n+1)<<3);
79
    iinit();
80
    rep(i,2,n-1) {
81
        Tr.insert(pre[i-1],1);
82
        pair<int,int> t=calc(i);
83
        int p=t.first, q=t.second;
84
        int c0=(q+1)/2, c1=q-c0;
85
        int p0=suf[p+1], p1=suf[p-i+1];
86
        if(p==n) {
87
            --c0;
88
            if(p-2*i>=i) p0=suf[p-2*i+1];
89
            else p0=0;
90
        }
91
        ans+=c0*Tr.query(p0)+c1*Tr.query(p1);
92
    }
93
    printf("%lld\n",ans);
94
}
95
signed main() {
96
    T=read();
97
    while(T--) solve();
98
}