形式化题面如下：

多组测试数据TT，给出一个字符串ss，求多少个相距为gg 的子串是相同的。
1≤T≤10,1≤g≤10,1≤s≤5×1041\le T \le 10,1\le g \le 10,1\le s \le 5\times 10^4

看到子串，并且要O(nlog⁡n)O(n \log n)，首先想到的就是 SA 和 SAM。

让后如果你做过 P1117 [NOI2016] 优秀的拆分的话，你会发现这个题和那个题很相似，都是在统计子串，不过这里有了距离限制。

我们考虑枚举子串长度LL，设第一段起始点为ll，那么第一段范围为[l,l+L−1][l,l+L-1]。第二段起始点rr 就是r=l+L+gr=l+L+g，同理[r,r+L−1][r,r+L-1]。那么它们什么时候才能够作为子串相同呢，这里有一个结论就是它们两端的 LCS（最长公共后缀） 与 LCP（最长公共前缀）的长度和（注意算重两个端点要减一）大于等于我们枚举的长度，也就是LCS⁡(l,r)+LCP⁡(l,r)−1≥L\operatorname{LCS}(l,r)+\operatorname{LCP}(l,r)-1\ge L。那么我们可以枚举起始点ll，rr 可以O(1)O(1) 算出来，利用 SA 或 SAM 能够O(1)→O(log⁡n)O(1)\to O(\log n) 查出它们的 LCS 和 LCP。

我们考虑怎么优化，注意到我们实际上就是在拿一个长为LL 的滑块在去滑，如果[l,l+L−1][l,l+L-1] 可以的话，那么我们在枚举[l+1,l+L−1][l+1,l+L-1] 实际上是没必要的，因为LCS⁡(l,r)+LCP⁡(l,r)−1≥L\operatorname{LCS}(l,r)+\operatorname{LCP}(l,r)-1\ge L 一但合法，若等于LL 那么说明 LCS 和 LCP 恰好碰到一起，就是 1 个，而一旦重合，那么说明这个字符串区间我们可以向后拓展几位也是合法的，那么最多能拓展多少呢？每一次向后拓展 LCS 与 LCP 都会减一，那么最多只能拓展LCS⁡(l,r)+LCP⁡(l,r)−1−L+1\operatorname{LCS}(l,r)+\operatorname{LCP}(l,r)-1-L+1 次，原题目只让我们统计合法的个数，所以一个滑块的答案是可以O(1)O(1) 算出来的。

这样的话，我们可以直接跳到l+Ll+L 开始枚举，这种方法相当于将字符串分成了∣s∣L\dfrac{|s|}{L} 的块，根据调和级数原理 ：

∣s∣1+∣s∣2+⋯+∣s∣∣s∣=∣s∣×(11+12+⋯+1∣s∣)≈O(nlog⁡n)\dfrac{|s|}{1}+\dfrac{|s|}{2}+\dots+\dfrac{|s|}{|s|}=|s|\times(\dfrac{1}{1}+\dfrac{1}{2}+\dots+\dfrac{1}{|s|})\approx O(n \log n)

那么时间复杂度就是O(nlog⁡n)O(n \log n)，对于 SA 可以做到O(nlog⁡n)O(n \log n) 预处理 LCP，SAM 预处理就是两个 endpos 集合在 link 树上的 LCA，可以做到O(nlog⁡n)O(n \log n) 预处理，O(1)→O(log⁡n)O(1) \to O(\log n) 查询 LCA，时间复杂度为O(nlog⁡n)→O(nlog⁡2n)O(n \log n)\to O(n \log^2 n)。

这种技巧是对字符串的分块思想。如果题目中出现一些构造字符串循环构成的问题，我们可以不妨考虑枚举这个循环的长度LL，让后按照LL 将字符串划分关键点分块（即按照LL 的倍数分块）利用分块和字符串的重复性质，将看似全局的问题局部化解决。对应到后缀数组上就是对相邻两块的块进行 LCP 和 LCS 查询。

文尾推销自己万字全家桶：后缀数组全家桶-从哈希乱搞到入门 - 洛谷专栏。

SAM 实现如下，用树刨求 LCA 时间复杂度O(nlog⁡2n)O(n \log^2 n)。

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
118
119
120
121
122
123
#include<bits/stdc++.h>
using namespace std;
constexpr int MN=5e5+15;
int n,g,casetot;
string s;

struct SAM{
    int nxt[MN][26],len[MN],pos[MN],fa[MN],tot,lst;
    int siz[MN],dep[MN],hson[MN],htop[MN];
    vector<int> adj[MN];

    void init(){
        for(int i=0;i<=tot;i++){
            adj[i].clear();
            len[i]=fa[i]=0;
            siz[i]=dep[i]=hson[i]=htop[i]=0;
            memset(nxt[i],0,sizeof(nxt[i]));
        }
        tot=lst=1;
    }

    void expand(int c,int id){
        int cur=++tot;
        len[cur]=len[lst]+1;
        pos[id]=cur;
        int p=lst;
        while(p&&!nxt[p][c]) nxt[p][c]=cur,p=fa[p];
        if(!p){
            fa[cur]=1;
        }else{
            int q=nxt[p][c];
            if(len[q]==len[p]+1){
                fa[cur]=q;
            }else{
                int nq=++tot;
                len[nq]=len[p]+1;
                fa[nq]=fa[q];
                memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
                fa[cur]=fa[q]=nq;
                while(p&&nxt[p][c]==q) nxt[p][c]=nq,p=fa[p];
            }
        }
        lst=cur;
    }

    void dfs1(int u,int pre){
        siz[u]=1;
        dep[u]=dep[pre]+1;
        for(auto v:adj[u]){
            dfs1(v,u);
            siz[u]+=siz[v];
            if(!hson[u]||siz[hson[u]]<siz[v]) hson[u]=v;
        }
    }

    void dfs2(int u,int ltop){
        htop[u]=ltop;
        if(!hson[u]) return;
        dfs2(hson[u],ltop);
        for(auto v:adj[u]){
            if(v==hson[u]) continue;
            dfs2(v,v);
        }
    }

    void inittree(){
        for(int i=2;i<=tot;i++){
            adj[fa[i]].push_back(i);
        }
        dfs1(1,0);
        dfs2(1,1);
    }

    int lca(int x,int y){
        while(htop[x]!=htop[y]){
            if(dep[htop[x]]<dep[htop[y]]) swap(x,y);
            x=fa[htop[x]];
        }
        return dep[x]<dep[y]?x:y;
    }

    int lcs(int x,int y){
        x=pos[x],y=pos[y];
        return len[lca(x,y)];
    }

}sam1,sam2;

void solve(){
    sam1.init();
    sam2.init();
    cin>>g>>s;
    n=s.length();
    s=" "+s;
    for(int i=1;i<=n;i++){
        sam1.expand(s[i]-'a',i);
    }
    for(int i=n;i>=1;i--){
        sam2.expand(s[i]-'a',i);
    }
    sam1.inittree();
    sam2.inittree();
    int ans=0;
    for(int j=1;j<=(n-g)>>1;j++){
        for(int i=1;i+j+g<=n;i+=j){
            int l=i,r=i+j+g;
            int lcs=min(sam1.lcs(l,r),j),lcp=min(sam2.lcs(l,r),j);
            int len=lcs+lcp-1;
            if(len>=j) ans+=len-j+1;
        }
    }
    cout<<"Case "<<++casetot<<": "<<ans<<'\n';
}

int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}