luogu1368 工艺

题目链接

思路

\(sam\)练手题，将原串重复一遍插入到\(sam\)中，然后贪心走长度为n的一个路径即可。
不用担心会直接走到终点，根据\(sam\)的构造方式可以发现会先走到前面的路径。

代码

/*
* @author: wxyww
* @date:   2019-07-11 11:09:25
* @last modified time: 2019-07-11 11:20:42
*/
#include<cstdio>
#include<map>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 600000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int len,fa;
    map<int,int>ch;
}sam[n << 1];
int lst = 1,tot = 1;
void add(int c) {
    int cur = ++tot,p = lst;
    sam[cur].len = sam[p].len + 1;
    while(p && !sam[p].ch[c]) {
        sam[p].ch[c] = cur;
        p = sam[p].fa;
    }
    if(!p) sam[cur].fa = 1;
    else {
        int q = sam[p].ch[c];
        if(sam[q].len == sam[p].len + 1) sam[cur].fa = q;
        else {
            int clone = ++tot;
            sam[clone] = sam[q];
            sam[clone].len = sam[p].len + 1;
            while(p && sam[p].ch[c] == q) {
                sam[p].ch[c] = clone;
                p = sam[p].fa;
            }
            sam[q].fa = sam[cur].fa = clone;
        }
    }
    lst = cur;
}
int a[n];
int main() {
    int n = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    for(int i = 1;i <= n;++i) add(a[i]);
    for(int i = 1;i <= n;++i) add(a[i]);
    int p = 1;
    for(int i = 1;i <= n;++i) {
        printf("%d ",sam[p].ch.begin() -> first);
        p = sam[p].ch.begin() -> second;
    }
    return 0;
}