给出一个字符串
询问有多少个子串满足
出现至少两次，且不重叠。
做法：
建出SAM。
对每个节点维护最大的endpos位置L和最小的endpos位置R
然后对每个节点\(i\)，取\(min(R-L,len[i])-len[link[i]]\)就是对答案的贡献。
求和即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int nxt[maxn][26],link[maxn],len[maxn],lst=1,tot=1;
int L[maxn],R[maxn];
char s[maxn];
vector<int> g[maxn];
void init () {
for (int i=0;i<=tot;i++) {
for (int j=0;j<26;j++) {
nxt[i][j]=0;
}
link[i]=len[i]=0;
L[i]=1000000000;
R[i]=0;
g[i].clear();
}
lst=tot=1;
}
void sam_extend (char c) {
int cur=++tot;
len[cur]=len[lst]+1;
int p=lst;
while (p&&!nxt[p][c-'a']) {
nxt[p][c-'a']=cur;
p=link[p];
}
if (!p) link[cur]=1;
else {
int q=nxt[p][c-'a'];
if (len[p]+1==len[q]) {
link[cur]=q;
}
else {
int clone=++tot;
len[clone]=len[p]+1;
for (int i=0;i<26;i++) nxt[clone][i]=nxt[q][i];
link[clone]=link[q];
while (p&&nxt[p][c-'a']==q) {
nxt[p][c-'a']=clone;
p=link[p];
}
link[q]=link[cur]=clone;
}
}
lst=cur;
}
void dfs (int u) {
for (int v:g[u]) {
dfs(v);
L[u]=min(L[u],L[v]);
R[u]=max(R[u],R[v]);
}
}
int main () {
for (int i=0;i<maxn;i++) L[i]=1000000000;
while (1) {
scanf("%s",s);
if (strlen(s)==1&&s[0]=='#') break;
for (int i=0;i<strlen(s);i++) {
sam_extend(s[i]);
L[lst]=R[lst]=i;
}
for (int i=2;i<=tot;i++) g[link[i]].push_back(i);
dfs(1);
long long ans=0;
for (int i=2;i<=tot;i++) {
//printf("%d %d %d %d\n",L[i],R[i],len[i],len[link[i]]);
ans+=max(0,min(R[i]-L[i],len[i])-len[link[i]]);
}
printf("%lld\n",ans);
init();
}
}