Description
求一个字符串中出现次数大于 (1) 的所有子串的出现次数(按子串的字典序排序)。
Solution
建出 SAM 后 DFS 一遍,每走到一个结点,如果它的 (endpos) 集合大小 (>1) 就输出它
#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
struct SAM {
int len[N], ch[N][26], fa[N], ind, last;
int t[N], a[N], cnt[N], f[N];
SAM() { ind = last = 1; }
inline void extend(int id) {
int cur = (++ ind), p;
len[cur] = len[last] + 1;
cnt[cur] = 1;
for (p = last; p && !ch[p][id]; p = fa[p]) ch[p][id] = cur;
if (!p) fa[cur] = 1;
else {
int q = ch[p][id];
if (len[q] == len[p] + 1) fa[cur] = q;
else {
int tmp = (++ ind);
len[tmp] = len[p] + 1;
for(int i=0;i<2;i++) ch[tmp][i] = ch[q][i];
fa[tmp] = fa[q];
for (; p && ch[p][id] == q; p = fa[p]) ch[p][id] = tmp;
fa[cur] = fa[q] = tmp;
}
}
last = cur;
}
void calcEndpos() {
memset(t, 0, sizeof t);
for(int i=1; i<=ind; i++) t[len[i]]++;
for(int i=1; i<=ind; i++) t[i]+=t[i-1];
for(int i=1; i<=ind; i++) a[t[len[i]]--]=i;
for(int i=ind; i>=1; --i) cnt[fa[a[i]]]+=cnt[a[i]];
cnt[1] = 0;
}
void dfs(int p)
{
if(cnt[p]>1) cout<<cnt[p]<<endl;
for(int i=0;i<2;i++)
{
if(ch[p][i])
{
dfs(ch[p][i]);
}
}
}
} sam;
int main() {
ios::sync_with_stdio(false);
string str;
int n;
cin>>n;
cin>>str;
int t,k;
for(int i=0;i<str.length();i++)
sam.extend(str[i]-'0');
sam.calcEndpos();
sam.dfs(1);
}