来源：
CE1998
题目大意：
求字符串最小表示。
思路：
字符串复制一遍接在后面，构建SAM，然后每次跑小的转移。
跑n次以后就跑到了最小表示的末尾，用该状态的len值减去n就是最小表示的起始位置。
#include<string>
#include<iostream>
int n;
std::string s;
class SuffixAutomaton {
private:
static const int SIGMA_SIZE=;
struct State {
State *link,*trans[SIGMA_SIZE];
unsigned len,min_trans;
State(const int l) {
link=nullptr;
std::fill(&trans[],&trans[SIGMA_SIZE],nullptr);
min_trans=SIGMA_SIZE;
len=l;
}
};
State *root,*last;
unsigned idx(const int ch) {
return ch-'a';
}
void extend(const char ch) {
const unsigned w=idx(ch);
State *p=last,*new_p=new State(last->len+);
while(p!=nullptr&&p->trans[w]==nullptr) {
p->trans[w]=new_p;
p->min_trans=std::min(p->min_trans,w);
p=p->link;
}
if(p==nullptr) {
new_p->link=root;
} else {
State *q=p->trans[w];
if(q->len==p->len+) {
new_p->link=q;
} else {
State *new_q=new State(p->len+);
std::copy(&q->trans[],&q->trans[SIGMA_SIZE],new_q->trans);
new_q->min_trans=q->min_trans;
new_q->link=q->link;
q->link=new_p->link=new_q;
while(p!=nullptr&&p->trans[w]==q) {
p->trans[w]=new_q;
p=p->link;
}
}
}
last=new_p;
}
public:
void build() {
root=last=new State();
for(std::string::iterator i=s.begin();i<s.end();i++) {
extend(*i);
}
for(std::string::iterator i=s.begin();i<s.end();i++) {
extend(*i);
}
}
unsigned query() {
State *p=root;
for(unsigned i=;i<s.length();i++) {
p=p->trans[p->min_trans];
}
return p->len-s.length()+;
}
};
SuffixAutomaton sam;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin>>n;
for(int i=;i<n;i++) {
std::cin>>s;
sam.build();
std::cout<<sam.query()<<std::endl;
}
return ;
}