SAM详解3.1（关于2和3的习题）

SAM

推销一波前面的文章：

SAM详解1

SAM详解2(初级应用)

SAM详解3（SAM与AC自动机的相似性，SAM处理字符串匹配）

luogu5341

题目链接

精简题意：给你一个字符串和 $k$，求 出现了 $k$ 次的子串的长度 的出现次数 的最大值。

我们可以用 SAM 建出 parent tree，然后一遍 dfs 求出每个位置的 $sz$，也就是 $|edp|$。

然后对于 $sz$ 为 $k$ 的节点，用差分维护。

因为在前文中讲过：

当然，你想用线段树什么的也可以维护，只是数据范围是 $3\times 10^6$ 的，带个 $\log$ 可能要卡常。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,m,k;
string s;
int df[N];
struct SAM{int las,tn;int sz[N<<1];struct node{int ch[26],f,len;}a[N<<1];vector<int>E[N<<1];SAM(){ las=1,tn=1;}void cl(){for(int i=1;i<=tn;i++){E[i].clear(),sz[i]=0,a[i].f=a[i].len=0;for(int j=0;j<26;j++)a[i].ch[j]=0;}las=1,tn=1;}void addE(int x,int y){E[x].push_back(y);}void dfs(int u){for(int v:E[u]){dfs(v);sz[u]+=sz[v];}if(sz[u]==k)df[a[a[u].f].len+1]++,df[a[u].len+1]--;}void btr(){for(int i=2