记录编号	338087	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] Glass Beads	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.487 s
提交时间	2016-11-05 07:43:04	内存使用	115.64 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <iostream>
using namespace std;
//最小表示法...
#define MAXN 300003
class SAM
{
public:
    int size, last;
    struct node
    {
        int len, link;
        int next[26];
        void init()
        {
            len = 0;
            link = -1;
            memset(next, 0, sizeof(next));
        }
    }st[MAXN<<2];
    int newst()
    {
        st[size++].init();
        return size-1;
    }
    SAM()
    {
        last = size = 0;
        newst();
    }
    void expand(int c)
    {
        int cur = newst();
        st[cur].len = st[last].len+1;
        int p;
        for(p = last; ~p && !st[p].next[c]; p = st[p].link)
            st[p].next[c] = cur;
        if(p == -1)
            st[cur].link = 0;
        else
        {
            int q = st[p].next[c];
            if(st[q].len == st[p].len + 1)
                st[cur].link = q;
            else
            {
                int clone = newst();
                st[clone].link = st[q].link;
                st[clone].len = st[p].len+1;
                memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
                for(; ~p && st[p].next[c] == q; p = st[p].link)
                    st[p].next[c] = clone;
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
}sam;
int main()
{
    freopen("MinRepresentations.in", "r", stdin);
    freopen("MinRepresentations.out", "w", stdout);
    int n;
    string s;
    cin >> n >> s;
    for(int k = 0; k < 2; k++)
    for(int i = 0; i < n; i++)
        sam.expand(s[i]-'a');
    int t = 0;
    int c = 0;
    for(int i = 0; i < sam.size; i++)
    {
        for(int j = 0; j < 26; j++)
            if(sam.st[t].next[j])
            {
                putchar('a'+j);
                c++;
                t = sam.st[t].next[j];
                break;
            }
        if(c == n)break;
    }
    return 0;
}