luoguP1368 工艺(最小表示法 后缀自动机）

最小表示法就是直接扫过去

后缀自动机就是每次找最字典序最小儿子输出

• 最小表示法

/*
最小表示法裸题， 我好像学过来着？？ 怎么忘得这么干净*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define ll long long
#define M 300010
#define mmp make_pair
using namespace std;
int read()
{
int nm = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
return nm * f;
}
int s[M];int work(int n)
{
int i = 0, j = 1, k = 0;
while(i < n && j < n && k < n)
{
int t = s[(i + k) % n] - s[(j + k) % n];
if(t == 0)
{
k++;
}
else
{
if(t > 0) i += k + 1;
else j += k + 1;
if(i == j) j++;
k = 0;
}
}
return i < j ? i : j;
}int main()
{
int len = read();
for(int i = 0; i < len; i++) s[i] = read();
int x = work(len);
int tmp = -1;
for(int y = x; y != tmp; y = (y + 1) % len)
{
cout << s[y] << " ";
tmp = x;}
return 0;
}

• 后缀自动机

/*
最小表示法裸题， 我好像学过来着？？ 怎么忘得这么干净*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#include<map>
#define ll long long
#define M 300010
#define mmp make_pair
using namespace std;
int read()
{
int nm = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
return nm * f;
}
int s[M];
int len[4 * M], fa[4 * M], cnt = 1, lst = 1;
map<int, int> ch[4 * M];
void insert(int c)
{
int p = ++cnt, f = lst;
lst = p;
while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];
if(!f)
{
fa[p] = 1;
}
else
{
int q = ch[f][c];
if(len[q] == len[f] + 1)
{
fa[p] = q;
}
else
{
int nq = ++cnt;
fa[nq] = fa[q];
ch[nq] = ch[q];
len[nq] = len[f] + 1;
fa[p] = fa[q] = nq;
while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];
}
}
}int main()
{
int len = read();
for(int i = 0; i < len; i++) s[i] = read(), insert(s[i]);
for(int i = 0; i < len; i++) insert(s[i]);
int now = 1;
for(int i = 0; i < len; i++)
{
cout << ch[now].begin()->first << " ";
now = ch[now].begin()->second;
}
return 0;
}