【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;

}

巴特西

【LG1368】工艺

【LG1368】工艺

题面

题解

代码

最新文章

热门文章