【LG1368】工艺

题面

洛谷

题解

好套路的一道题。。。

我们倍长这个字符串，然后我们要查询的串就为这个倍长过后串的长度\(n\)一个子串，要求字典序最小

然后就可以非常愉快地后缀排序了

后缀的话，直接往每个状态的字典序最小的后继状态跑就行了。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <cmath> 
#include <algorithm>
#include <map> 
using namespace std; 
inline int gi() {
    register int data = 0, w = 1;
    register char ch = 0;
    while (!isdigit(ch) && ch != '-') ch = getchar(); 
    if (ch == '-') w = -1, ch = getchar(); 
    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); 
    return w * data; 
} 
const int MAX_N = 3e5 + 5; 
struct Node { 
    map<int, int> ch; 
    int len, fa; 
} t[MAX_N << 2];
int tot = 1, lst = 1; 
void extend(int c) { 
    ++tot, t[lst].ch[c] = tot; 
    t[tot].len = t[lst].len + 1; 
    int p = t[lst].fa; lst = tot;
    while (p && t[p].ch.find(c) == t[p].ch.end()) t[p].ch[c] = tot, p = t[p].fa; 
    if (!p) t[tot].fa = 1; 
    else { 
        int q = t[p].ch[c]; 
        if (t[q].len == t[p].len + 1) t[tot].fa = q; 
        else { 
            int _q = ++tot; t[_q] = t[q]; 
            t[tot - 1].fa = t[q].fa = _q, t[_q].len = t[p].len + 1; 
            while (p) { 
                map<int, int> :: iterator ite;
                ite = t[p].ch.find(c); 
                if (ite == t[p].ch.end() || ite->second != q) break; 
                t[p].ch[c] = _q;
                p = t[p].fa; 
            } 
        } 
    } 
}
int N, a[MAX_N]; 
int main () {
#ifndef ONLINE_JUDGE 
    freopen("cpp.in", "r", stdin);
    freopen("cpp.out", "w", stdout);
#endif 
    N = gi();
    for (int i = 1; i <= N; i++) a[i] = gi(); 
    for (int i = 1; i <= N; i++) extend(a[i]);
    for (int i = 1; i <= N; i++) extend(a[i]); 
    int v = 1; 
    for (int i = 1; i <= N; i++) { 
        printf("%d ", t[v].ch.begin()->first); 
        v = t[v].ch.begin()->second; 
    }
    putchar('\n'); 
    return 0; 
}