我承认我是个傻逼
也只有我这么离谱会用(SAM)来求(SA)了
对这道题来说，还是比较简单的，只需要复制原串一遍贴到后面，然后求一遍(SA)即可
接下来我给诸位介绍一下我研究了两个下午，然后(MLE)的成果
首先我们对字符串建出(SAM)，考虑S(AM)的本质是一个(DAG)图和一棵后缀树
因为我们要对后缀进行排序，所以我们要尽可能的利用后缀树来解决问题
很明显在后缀树上按字典序遍历即可得到(SA)
所以我们现在的问题就是如何解决如何按字典序遍历
求出其父节点与自身加长的串中第一个字符大小，用它来排序
然后加边(dfs)即可
算了我来给你们翻译一下(solve)函数
inline void solve()
{
for(int i=1;i<=cnt;i++) link[i] = ge(c[n + 1 - Right[i] + node[node[i].fa].len]) , bac[link[i]]++;//求出第一个字符
for(int i=1;i<=256;i++) bac[i]+= bac[i-1];
for(int i=1;i<=cnt;i++) Ti[bac[link[i]]--] = i;//相当于把所有link都丢进64个桶里，节点越大在对应的桶里越靠后
for(int i=cnt;i>=1;i--) add(node[Ti[i]].fa , Ti[i]);//倒着加边意味着z类边优先加入
}
(Code)
#include<bits/stdc++.h>
using namespace std;
#define INF 1ll<<30
#define ill long long
#define sto set<node>::iterator
template<typename _T>
inline void read(_T &x)
{
x=0;char s=getchar();int f=1;
while(s<'0'||s>'9') {f=1;if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
x*=f;
}
int ge(char ch)
{
if (ch<='9' && ch>='0') return ch-'0';
if (ch<='Z' && ch>='A') return ch-'A'+10;
if (ch<='z' && ch>='a') return ch-'a'+36;
return ch;
}
const int np = 2e5+5;
struct SAM{
int fa;
int len;
int son[80];
int pos;
}node[np * 2];
int cnt = 1 , la = 1,n;
int Right[np * 2];
inline void insert(int x,int i)
{
int k,p,q,now;
p = la,now = la = ++cnt;
Right[now] =node[now].len = node[p].len + 1, node[now].pos = i;
for( ;p && !node[p].son[x] ;node[p].son[x] = now , p = node[p].fa );
if(!p) return (void)(node[now].fa = 1);
if(node[p].len + 1 == node[q = node[p].son[x] ].len) return (void)(node[now].fa = q);
node[k = ++cnt].len = node[p].len + 1 , node[k].fa = node[q].fa ; node[q].fa = node[now].fa = k,Right[k] = Right[q] ,memcpy(node[k].son , node[q].son , sizeof(node[q].son));
for( ; p&& !(node[p].son[x] ^ q) ; node[p].son[x] = k , p = node[p].fa) ;
}
int link[np * 2] , bac[np * 2];
int Ti[np * 2],head[np * 2] , nxt[np * 2] , ver[np *2];
int tit;
char c[np * 2];
inline void add(int a,int b)
{
ver[++tit] = b;
nxt[tit] = head[a];
head[a] = tit;
}
inline void solve()
{
for(int i=1;i<=cnt;i++) link[i] = ge(c[n + 1 - Right[i] + node[node[i].fa].len]) , bac[link[i]]++;
for(int i=1;i<=256;i++) bac[i]+= bac[i-1];
for(int i=1;i<=cnt;i++) Ti[bac[link[i]]--] = i;
for(int i=cnt;i>=1;i--) add(node[Ti[i]].fa , Ti[i]);
}
int sa[np * 2];
int gs = 0;
inline void dfs(int x)
{
if(node[x].pos) sa[++gs] = node[x].pos;
for(int i=head[x];i;i=nxt[i])
dfs(ver[i]);
}
signed main()
{
scanf("%s",c+1);
n = strlen(c+1);
int Len = n;
for(int i=1;i<=n;i++)
c[i + n] = c[i];
n = strlen(c + 1);
for(int i=n;i>=1;i--) insert(ge(c[i]) , i);
solve();
dfs(1);
for(int i=1;i<=gs;i++)
{
if(sa[i] > Len) continue;
else
{
cout<<c[sa[i] + Len - 1];
}
}
}
(End)
事实证明(SAM)的最大阻力就是空间太小
在(10^6)以内(128MB)是解决不了问题的
开(map)也没用