2021 icpc 沈阳 M（后缀自动机）

题意：给定一个串串，求每个前缀的子串中字典序最大子串出现在的最左边的位置。
思路：其实看到子串看到字典序，很容易联想到桂林的那个J，很自然的反串建后缀自动机，然后建好parent树，边权是较父亲刚好多出的字符，然后dfs序就是字典序了，具体看上一篇桂林的博客。之后怎么求呢，考虑每一个子串的贡献，也就是对于每一个子串，以他为最大字典序的子串的右端点一定在它的右端点右边（好像一句废话），那么我们在parent数上沿dfs序递增遍历的时候，由于子串字典序越来越大了，那么当前子串的贡献必然可以覆盖前面的所有子串，也就是当前子串的右端点右边的所有后缀都会被当前子串覆盖，可以线段树维护，也可以搞个标记数组，记录下time，最后覆盖下就行，记录覆盖信息的时候我们很容易想到对于一个子串，其最大字典序子串必然是其后缀，所以我们只需要记录左端点就行了。注意，为了能够尽量覆盖到多的子串，我们在构建后缀自动机的时候对每一个子串的位置应该尽量大，因为我们是反串建的，所以对于原串就是尽量小，这样就可以尽可能覆盖到多的子串。
吐槽一下赛中的窒息操作，忘记输入，倒置字符串的时候1到n交换，结果等于没转，tim从0开始记的，最后最小值也定了个0，结果tim为0的信息都没获取到。

#include 
#define de(x) cerr << "  debug  " << #x << "  ==  " << x << endl;
#define ll long long

using namespace std;

const int maxn = 1e6 + 7;
struct state
{
    int len, link;
    int nxt[26];
    int id;
    int pos;
} st[maxn * 2];
int sz, last;
void sam_init()
{
    memset(st[0].nxt, 0, sizeof(st[0].nxt));
    sz = 0;
    st[0].len = 0;
    st[0].link = -1;
    sz++;
    last = 0;
}
int cur;
void sam_extend(char c, int id)
{
    cur = sz++;
    st[cur].len = st[last].len + 1;
    st[cur].pos = id;
    int p = last;
    while (p != -1 && !st[p].nxt[c - 'a'])
    {
        st[p].nxt[c - 'a'] = cur;
        p = st[p].link;
    }
    if (p == -1)
    {
        st[cur].link = 0;
    }
    else
    {
        int q = st[p].nxt[c - 'a'];
        if (st[p].len + 1 == st[q].len)
        {
            st[cur].link = q;
        }
        else
        {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            memcpy(st[clone].nxt, st[q].nxt, sizeof(st[clone].nxt));
            st[clone].link = st[q].link;
            while (p != -1 && st[p].nxt[c - 'a'] == q)
            {
                st[p].nxt[c - 'a'] = clone;
                p = st[p].link;
            }
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
int len[maxn*2];
int a[maxn*2];
int n;
void getSiz()
{
    for (int i = 1; i < sz; i++)
    {
        len[st[i].len]++;
    }
    for (int i = n; i >= 1; i--)
    {
        len[i] += len[i + 1];
    }
    for (int i = 1; i < sz; i++)
    {
        a[len[st[i].len]--] = i;
    }
    for (int i = 1; i < sz; i++)
    {
        int p = a[i];
        st[st[p].link].pos = max(st[st[p].link].pos, st[p].pos);
    }
}
char s[maxn];
struct node
{
    int str;
    int x;
    node(int ss, int xx)
    {
        str = ss;
        x = xx;
    }
};
vector v[maxn*2];
bool cmp(node a, node b)
{
    return a.str < b.str;
}
pair P[maxn];
int tim;
void dfs(int x)
{
    if (x != 0)
    {
        int l = n - st[x].pos + 1;
        int r = l + st[st[x].link].len;
        P[r] = make_pair(tim++, l);
    }
    for(auto i: v[x])
    {
        dfs(i.x);
    }
   // for (int i = 0; i < 26; i++)
   // {
   //     if (st[x].nxt[i])
  //      {
  //          dfs(st[x].nxt[i]);
   //     }
  //  }
}
int main()
{
    scanf("%s",s+1);
    n = strlen(s + 1);
    for (int i = 1; i <= n/2; i++)
    {
        swap(s[i], s[n - i + 1]);
    }
    sam_init();
    for (int i = 1; i <= n; i++)
    {
        sam_extend(s[i], i);
    }
    getSiz();
    for (int i = 1; i < sz; i++)
    {
        v[st[i].link].push_back(node(s[st[i].pos - st[st[i].link].len] - 'a', i));
    }
    for (int i = 0; i < sz; i++)
    {
        sort(v[i].begin(), v[i].end(), cmp);
    }
    dfs(0);
    int ans = 1;
    int tt = 0;
   // cout< tt)
        {
            tt = P[i].first;
            ans = P[i].second;
        }
        printf("%d %d\n", ans, i);
    }
    #ifdef iyua
        system("pause");
    #endif 
    return 0;
}