来源：
CE1998
题目大意：
求字符串最小表示。
思路：
字符串复制一遍接在后面，构建SAM，然后每次跑小的转移。
跑n次以后就跑到了最小表示的末尾，用该状态的len值减去n就是最小表示的起始位置。
1 #include<string> 2 #include<iostream> 3 int n; 4 std::string s; 5 class SuffixAutomaton { 6 private: 7 static const int SIGMA_SIZE=26; 8 struct State { 9 State *link,*trans[SIGMA_SIZE]; 10 unsigned len,min_trans; 11 State(const int l) { 12 link=nullptr; 13 std::fill(&trans[0],&trans[SIGMA_SIZE],nullptr); 14 min_trans=SIGMA_SIZE; 15 len=l; 16 } 17 }; 18 State *root,*last; 19 unsigned idx(const int ch) { 20 return ch-'a'; 21 } 22 void extend(const char ch) { 23 const unsigned w=idx(ch); 24 State *p=last,*new_p=new State(last->len+1); 25 while(p!=nullptr&&p->trans[w]==nullptr) { 26 p->trans[w]=new_p; 27 p->min_trans=std::min(p->min_trans,w); 28 p=p->link; 29 } 30 if(p==nullptr) { 31 new_p->link=root; 32 } else { 33 State *q=p->trans[w]; 34 if(q->len==p->len+1) { 35 new_p->link=q; 36 } else { 37 State *new_q=new State(p->len+1); 38 std::copy(&q->trans[0],&q->trans[SIGMA_SIZE],new_q->trans); 39 new_q->min_trans=q->min_trans; 40 new_q->link=q->link; 41 q->link=new_p->link=new_q; 42 while(p!=nullptr&&p->trans[w]==q) { 43 p->trans[w]=new_q; 44 p=p->link; 45 } 46 } 47 } 48 last=new_p; 49 } 50 public: 51 void build() { 52 root=last=new State(0); 53 for(std::string::iterator i=s.begin();i<s.end();i++) { 54 extend(*i); 55 } 56 for(std::string::iterator i=s.begin();i<s.end();i++) { 57 extend(*i); 58 } 59 } 60 unsigned query() { 61 State *p=root; 62 for(unsigned i=0;i<s.length();i++) { 63 p=p->trans[p->min_trans]; 64 } 65 return p->len-s.length()+1; 66 } 67 }; 68 SuffixAutomaton sam; 69 int main() { 70 std::ios_base::sync_with_stdio(false); 71 std::cin.tie(NULL); 72 std::cin>>n; 73 for(int i=0;i<n;i++) { 74 std::cin>>s; 75 sam.build(); 76 std::cout<<sam.query()<<std::endl; 77 } 78 return 0; 79 }