子串周期查询问题学习笔记

123asdfghjkl · 2021-05-25 10:17:38 · 个人记录

子串周期查询问题学习笔记

1.约定

证明 ：不妨假设 p<q。由周期的定义可得

同理可得，s[i]=s[i+q]

若 i \leq p，那么s[i]=s[i+q]=s[i+q-p]

若p<i<|S|-q+p,那么S[i]=S[i-p]=S[i+q-p]

可得 q-p 也是一个周期，然后发现这个过程是在辗转相减，所以 GCD(p,q) 也是一个周期。

引理2 若串 S,T 满足 2|S|>=|T|，则 S 在 T 中的出现位置构成一个等差数列

证明：若 S 在 T 中出现了一次或两次，则引理已证完，因此只需考虑 S 在 T 中至少出现了 3 次。

对于两次出现位置 p < q ，由于 S 是 T[p . . . q + |S | − 1] 的 border，有 q − p 是 T[p . . . q+|S | −1] 的周期。同时根据 1 ≤ p, q ≤ |T| − |S |+ 1 ，有 p+|S | −1 ≥ |S | ≥ |T| − |S | ≥ q ，因此 q − p < |S| ，则 q − p 也是 S 的周期。

然后你就可以看图理解一下。

推论1 : LargePS (S, T) 的元素构成一个等差数列。

证明 ：考虑其中最大的元素 p ，则对于任意 q ∈ LargePS (S, T) ,有 pre f(S, q) 是 pre f(S, p) 的前缀，su f(T, q) 是 su f(T, p) 的后缀，因此 pre f(S, q) 是 pre f(S, p) 的 border。可由引理3易得。

推论2：对于一个串 S 和整数 k ≤ \frac{|S |} 2 ，所有满足 k ≤ x < 2k 的 S 的 border 长度 x 构等差数列。

证明：上述 x 组成的集合恰好为 LargePS (pre f(S, 2k), su f(S, 2k)) 。

根据推论2，我们有个大致的想法：

回到原问题，若求一个子串 S 的 per(S),也相当于求 S 的所有 bored，我们可以把这些 bored 分为 log|s| 类，第 i 类的长度在 [2^{\lfloor {log_2|S|}\rfloor},2^i) ,对于这一类，我们要求的也就是 LargePS (pre f(|S |, 2 ^i ), su f(|S |, 2 ^i ))

引理4：

对于 2^{k−1} ≤ x < |S | = |T| = 2^k ，x ∈ LargePS (S, T) 当且仅当 su f(pre f(S, x), 2 ^{k−1} ) = su f(T, 2^ {k−1} ) ，且对应地 pre f(su f(T, x), 2^{k−1} ) = pre f(S, 2^{k−1} ) 。

有了这个引理，我们先求出 pre f(|S |, 2 ^{i−1} ) 在 su f(|S |, 2 ^i ) ，以及 su f(|S |, 2^{ i−1} ) 在 pre f(|S |, 2 ^i ) 的所有出现位置，均使用等差数列表示。

然后 LargePS (pre f(|S |, 2 ^i ), su f(|S |, 2 ^i )) 就是两个等差数列移位后的交。

考虑怎么求出 pre f(|S |, 2 ^{i−1} ) 在 su f(|S |, 2 ^i ) 的所有出现位置。

由引理1可知，我们只需要求出等差数列即可，我们可以只求出第一次、第二次和最后一次出现位置，就能求出 pre f(|S |, 2 ^{i−1} ) 在 su f(|S |, 2 ^i ) 的所有出现位置，su f(|S |, 2^{ i−1} ) 在 pre f(|S |, 2 ^i ) 的所有出现位置同理可得。

具体实现：

实现 succ(S, i) 和 pred(S, i) 操作，即找到 i 位置之后或之前（包括其本身）的 S 串的第一次出现位置。

具体地，假设母串是 T ，前者是 S 1 = T[l . . .r] ，后者是 S 2 = T[l ′ . . .r ′ ] ，其中 2(r − l + 1) = r ′ − l ′ + 1 。令 s = succ(S 1, l ′ ), d = succ(S 1, s + 1) − s, t = pred(S 1,r ′ − |S 2| + 1) 。要求的等差数列就是首项是 s ，末项是 t ，公差是 d 的等差数列。

为了实现 succ 操作，我们可以把所有长度为 2^t 的子串中相等的串 T 的所有出现位置保存在同一个有序表内，记为 pos(T,t)，然后很容易能够二分找到第一个位置。

4.2 等差数列求交及优化

对于一般问题，若求 (s1,d1,k1) 和 (s2,d2,k2) 的公共部分，一般只能求出 s1+xd1=s2+yd2 的解，并截取某一段，可以用 exgcd 解，复杂度 O(\log \max(|d1|,|d2|)) 。

但是字符串有特殊的性质，让我们可以 O(1) 求交。

引理5：若四个字符串满足 |x1| = |y1| ≥ |x2| = |y2| ，且 x1 在 y2y1 中至少匹配 3 次，y1 在 x1 x2 中至少匹配 3 次，则 minper(x1) = minper(y1) 。

这直接说明了：若 pre f(|S |, 2 ^{i−1} ) 在 su f(|S |, 2 ^i ) ，以及 su f(|S |, 2^{ i−1} ) 在 pre f(|S |, 2 ^i ) 的出现次数都大于3，那么公差相等，即d1=d2。

证明：

用反证法，假设 minper(x1) , minper(y1) 。若 minper(x1) > minper(y1) ，考虑 x1 在 y2y1 中最后一次匹配位置，令其与 y1 的重叠部分为 z 。

根据引理 2，可知 x1 在 y2y1 中相邻两次匹配的间距恰好为 minper(x1) ，又有 |y2| ≤ |x1| ，可得 |y2| + |z| ≥ |x1| + 2minper(x1) ≥ |y2| + 2minper(x1) ，即 |z| ≥ 2minper(x1) 。

此时可以发现，z 有周期 minper(x1) 和 minper(y1) ，而 |z| ≥ 2minper(x1) ≥ minper(x1)+ minper(y1) ，根据引理1，z 有周期 d = gcd(minper(x1), minper(y1)) | minper(x1) ，因此 d 也是 x1 的周期，与 minper(x1) 产生了矛盾。

而当 minper(x1) < minper(y1) 时产生矛盾的过程也几乎一致，只有“翻转”意义下的区别，故不再重复。上述矛盾表明 minper(x1) = minper(y1) 。 □

若 k1 < 3 或 k2 < 3 ，可以直接枚举对应等差数列里的所有元素并判断是否在另一个等差数列内，否则根据引理 5，d1 = d2 ，可以直接 O(1) 地求出等差数列的交。

如果实在看不懂这个证明，你可以直接取这种情况的特殊情况，及即 y1y2=suf(|S|,2^i),x1=pref(|S|,2^{i-1}) ，这就是我们最终用到的东西，这时 |x1|=|y1|=|y2|=|x2|=2^{i-1} ,再结合引理5就很显然了。

4.3 succ 和 pred 查询的优化

我们已经把等差数列求交优化成 O(1) 的了，发现瓶颈在于求 succ 和 pred 因为这两个还是 O(\log n) 的，如果不优化，总时间复杂度会是 O(n\log^2n) 。

我们不想二分，怎么办呢？

考虑对于每个本质不同的长度为 2^t 的子串，即基本子串字典里同一行中 name 不相同的串 T ，我们记 seg(T,x) 为 T 在母串 S 的所有在区间 [2^t · (x − 1) + 1, 2 ^t · x] 的出现位置，这可以用一个等差数列表示。（seg(T,x) 要用哈希表）

关于找等差数列，就直接在用 pos(T,t) 那个东西扫过去就好了，总时间复杂度 O(n\log n)

4.4 完结撒花

5.基本子串字典的扩展与应用

因为找不到原题，而且懒得自己造数据，我觉得应该放一下基本子串字典的板子题来熟悉代码实现。

例1

给定串 S ，每次查询给出 i, j, i ′ , j ′ ，要求比较 S [i . . . j] 和 S [i ′ . . . j ′ ] 的大小。

解，若 j-i!=j'-i' 那么两个子串不可能相等，可以把较长的子串的后面若干位删去使得和较短的子串长度相同，并做一次新询问。若新询问的回答是不相等，则原询问的回答和新询问的回答相同，否则原询问的回答是较长的子串更大。

现在假设 j-i=j'-i' 找到 2^t<j-i+1<=2^{t-1} ，可以通过比较 Name_m [i] 与 Name_m [ j] 和比较 Name_m [ j − 2 m + 1] 与 Name_m [ j ′ − 2 m + 1] 完成。预处理 O(n\log n) ，查询 O(1) 。

update 我找到了 /kel 真.板子 https://acm.nflsoj.com/problem/338

#include<bits/stdc++.h>
#define N 400010
using namespace std;
char c[N];
int lg2[N],sa[N],oldrk[N*2],rk[N],name[21][N],cnt[N],pk[N],id[N],n,m;
vector<int>v[21][200001];
char obuf[1<<23],*O=obuf;
#define putchar(c) (*O++=c)
inline int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=x*10+int(ch-48);
        ch=getchar(); 
    }
    return x;
}
void fw(int x){
    if(x>=10)fw(x/10);
    putchar(int(x%10)+48);
}
void init(){
    scanf("%s",c+1);
    n=strlen(c+1),m=27;
    lg2[0]=-1;
    for(int i=1;i<=n;i++)lg2[i]=lg2[i/2]+1;
    int maxx=lg2[n]+1;
    for(int i=1;i<=n;i++)cnt[name[0][i]=rk[i]=int(c[i]-'a'+1)]++;
    for(int i=2;i<=m;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
    for(int w=1,now=1;w<n;w<<=1,now++){
        int p=0;
        for(int i=n-w+1;i<=n;i++)id[++p]=i;
        for(int i=1;i<=n;i++)if(sa[i]>w)id[++p]=sa[i]-w;
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)cnt[pk[i]=rk[id[i]]]++;
        for(int i=2;i<=m;i++)cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;i--)sa[cnt[pk[i]]--]=id[i];
        p=0;
        memcpy(oldrk,rk,sizeof(rk));
        for(int i=1;i<=n;i++){
            if(oldrk[sa[i]]!=oldrk[sa[i-1]]||oldrk[sa[i]+w]!=oldrk[sa[i-1]+w])p++;
            rk[sa[i]]=p;
        }
        m=p;
        for(int i=1;i<=n;i++)if(sa[i]+w-1<=n)name[now][sa[i]]=rk[sa[i]];
    }
    for(int now=0;now<=maxx;now++){
        for(int j=1;j<=n-(1<<now)+1;j++)v[now][name[now][j]].push_back(j);
    }
}//name
struct jyytxdy{
    int s,t,d;
    jyytxdy(int s_=-1,int t_=-1,int d_=-1){
        s=s_,t=t_,d=d_;
    }
}o,res[N];
int find(jyytxdy a,int x){
    return a.s<=x&&a.t>=x&&((x-a.s)%a.d==0);
}
jyytxdy merge(jyytxdy a,jyytxdy b){
    if(a.d!=b.d){
        if(a.s+a.d>=a.t)swap(a,b);
        if(!find(a,b.s)){
            if(!find(a,b.t))return o;
            else return jyytxdy(b.t,b.t,1);
        }
        if(find(a,b.t))return b;
        return jyytxdy(b.s,b.s,1);
    }
    if(a.s>b.t||a.t<b.s||(a.s-b.s)%a.d)return o;
    return jyytxdy(max(a.s,b.s),min(a.t,b.t),a.d);
}
jyytxdy match(int l,int r,int d,int p){//在[l,r]中找长度为2^d,p开头的起始位置 
    if(l>r)return o;
    int rank=name[d][p];
    int s1=lower_bound(v[d][rank].begin(),v[d][rank].end(),l)-v[d][rank].begin();
    if(s1==(int)v[d][rank].size()||v[d][rank][s1]>r)return o;
    int s2=s1+1;
    if(s2==(int)v[d][rank].size()||v[d][rank][s2]>r)return jyytxdy(v[d][rank][s1],v[d][rank][s1],1);
    int D=v[d][rank][s2]-v[d][rank][s1];
    int t=upper_bound(v[d][rank].begin(),v[d][rank].end(),r)-v[d][rank].begin()-1;
    return jyytxdy(v[d][rank][s1],v[d][rank][t],D);
}
void solve(){
    int l=read()+1,r=read()+1;
    int tot=0;
    for(int now=0,w=1;w<=r-l;now++,w<<=1){
        jyytxdy a=match(l,min(r-w+1,l+w)-1,now,r-w+1);//[l,l+2*w-1],右区间+1是为了不取到长度为2*w的bored 
        if(a.d<0)continue;
        jyytxdy b=match(max(l,r-2*w+1)+1,r-w+1,now,l);//[r-2*w+1,r] 
        if(b.d<0)continue;
        a.s=a.s+w-1-(l-1),a.t=a.t+w-1-(l-1);//把位置转化为长度
        b.s=r-b.s+1,b.t=r-b.t+1,swap(b.s,b.t);
        a=merge(a,b);
        if(a.d>=0) res[++tot]=a;
    }
    if(!tot){
        putchar('-');
        putchar('1');
        putchar('\n');
        return;
    }
    int minn=res[1].s,maxx=res[tot].t,sum=0;
    for(int i=1;i<=tot;i++)sum+=(res[i].t-res[i].s)/res[i].d+1;
    fw(minn),putchar(' '),fw(maxx),putchar(' '),fw(sum),putchar('\n');
}
int T;
int main(){
    init();
    cin>>T;
    while(T--)solve();
    fwrite(obuf,O-obuf,1,stdout);
}