洛谷 1117 libreoj 2083 优秀的拆分 题解

发表于 | 阅读次数：
本文字数： 1.4k 字 | 阅读时长 ≈ 6 分钟

题意简述

一个字符串是“优秀”的，定义为：存在两个非空的字符串 $A,B$，满足这个字符串 $S=AABB$，那么这个 $S$ 就是优秀的。

给定一个串，计算它有多少子串是“优秀”的。相同的子串出现在不同的位置也被算两次。

长度 $\le 3e4$

思路

对于每个位置，我们维护 $pre[i]$ 表示以 $i$ 结尾的 $AA$ 形式的串有多少个，$suf[i]$ 同理。

然后答案就是 $\prod\limits_{i=1}^{n-1}pre[i]\times suf[i+1]$

然后考虑怎么求 $pre$。（$suf$ 的话，就把串反过来求一遍 $pre$ 即可）

如何求 pre

不会吧？不会就对了，黑题是这么容易做出来的嘛。 我们继续降低要求，我们求特定长度的 $pre[i]$。我们设 $A$ 的长度为 $k$，也就是 $AA$ 串的长度为 $2k$ 。 这个好判断，哈希就行了。 对于位置 $i$，如果 $[i-k+1,i]$ 区间的哈希值等于区间 $[i-2k+1,i-k]$ 的哈希值，那么 $pre[i]$ 就可以 $+1$，因为长度 $k$ 满足条件。

但是这样是 $O(n^2)$ 的呀，怎么更快速的求呢。

假如现在我们枚举 $k$，能很快的求出 $[1,n]$ 的答案，那多好啊。

那有了这样一个巧妙的做法（看题解前我也不会）：对于长度 $k$，我们在 $k,2k,3k…k\times (n/k)$ 的位置都打上一个标记。显然，标记的总数是 $(n/1)+(n/2)+(n/3)…+(n/n)=n\ln n$。

而且还有一个特性，一个长度为 $2k$ 的 $AA$ 串，把它分成等长度并且相同的两半，肯定各自覆盖到一个标记。

如这个图所示，蓝色是整个大串 $S$，黄色+绿色是一个串 $A$，黄色+绿色+黄色+绿色是一个 $AA$ 串。红色的是两个标记。

我们发现，黄色部分长度是两个标记的公共后缀长度之一，绿色部分则是两个标记的公共前缀长度之一。

对于每个标记，我们求出这个标记和上一个标记的最长公共前缀，和最长公共后缀（二分+哈希）。（当然，这最长公共前后缀的长度不能超过 $k$）设当前位置在 $p$，上一个标记位置是 $p-k$。 子串 $s[p,n]$ 和子串 $s[p-k,n]$ ，最长公共前缀为 $LCP$（Longest Common Prefix），子串 $s[1,p]$ 和子串 $s[1,p-k]$ 的最长公共后缀为 $LCS$。

那么这个 $AA$ 串，长度为 $2k$，左端点最左能到 $L=p-k-LCS+1$，右端点最右能到 $R=p+LCP-1$。那么这个 $AA$ 的右端点的范围就是 $[L+2k-1,R]$。当然，这个范围不能超过 $P$ ，注意和 $P$ 取一下 $\min$ 或者 $\max$。显然，对于这个区间的所有 $pre$ 数组都能 $+1$。（因为它是一个 $AA$ 串的右端点）

我们发现，前面都是加法操作，而只要维护一次查询（最后的总查询），用差分即可。

代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define mod 114514027ll //这模数太臭了
    #define int long long 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    int p[N];
    void Init()
    {
        p[0]=1; F(i,1,1e5) p[i]=(p[i-1]*31)%mod; // 31为底，质数，保险
    }
    char a[N]; int n;
    void Input()
    {
        scanf("%s",a+1); n=strlen(a+1);
    }
    int pre[N];
    int rangehash(int l,int r) {return (pre[l]-pre[r+1]*p[r-l+1]%mod+mod)%mod;} // 区间哈希值
    int LCS(int a,int b) //最长公共后缀长度
    {
        if (a>b) swap(a,b); 
        int l=1,r=b-a;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if (rangehash(a-mid+1,a)==rangehash(b-mid+1,b)) l=mid;
            else r=mid-1;
        }
        return l;
    }
    int LCP(int a,int b) // 最长公共前缀长度
    {
        if (a>b) swap(a,b);
        int l=1,r=b-a;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if (rangehash(a,a+mid-1)==rangehash(b,b+mid-1)) l=mid;
            else r=mid-1;
        }
        return l;
    }
    int L[N],R[N];
    // L 和 R 对应上面说的 suf 和 pre
    // L[i]: 以 i 为左端点（开头）的 AA 串有多少个
    // R[i]: 以 i 为右端点（结尾）的 AA 串有多少个
    void rangeadd(int c[],int l,int r){c[l]++; c[r+1]--;} // 差分数组 区间加
    void Soviet()
    {
        F(i,0,n+1) pre[i]=L[i]=R[i]=0;

        D(i,n,1) pre[i]=(pre[i+1]*31+(a[i]-'a'+1))%mod;
        F(len,1,n/2) Fs(i,2*len,n,i+=len)
        {
            if (a[i]!=a[i-len]) continue;
            int l=i-LCS(i,i-len)+1,r=i+LCP(i,i-len)-1;
            l=max(l+len-1,i);
            r=min(r,i+len-1); // 和 i 取一下min和max，注意范围
            if (l<=r) 
            {
                rangeadd(R,l-2*len+1,r-2*len+1);
                rangeadd(L,l,r);
            }
        }
        F(i,1,n) L[i]+=L[i-1],R[i]+=R[i-1]; // 最后可别忘了求前缀和
        int ans=0;
        F(i,1,n-1) ans+=L[i]*R[i+1]; // 答案式子
        printf("%lld\n",ans);
    }

    #define Flan void
    Flan IsMyWife()
    {
        int t;R1(t);
        Init();
        F(i,1,t)
        {
            Input();
            Soviet();
        }
    }
    #undef int //long long 
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w