【洛谷P1368】工艺

题面

https://www.luogu.org/problem/P1368

题解

#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
#define ri register int
#define N 300050
using namespace std;
int l;
struct node{
  int ff,len;
  map<int,int> ch;
} t[N<<2];

int a[N];
struct SAM {
  int tot,las;
  inline void init() {
    tot=las=1;
  }
  inline void extend(int c) {
    int np=++tot,p=las; las=tot;
    t[np].len=t[p].len+1;
    while (p && !t[p].ch[c]) t[p].ch[c]=np,p=t[p].ff;
    if (!p) {
      t[np].ff=1;
    }
    else {
      int q=t[p].ch[c];
      if (t[q].len==t[p].len+1) {
        t[np].ff=q;
      }
      else {
        int nq=++tot;
        t[nq]=t[q]; t[nq].len=t[p].len+1;
        t[np].ff=t[q].ff=nq;
        while (p && t[p].ch[c]==q) t[p].ch[c]=nq,p=t[p].ff;
      }
    }
  }
} sam;
int main(){
  sam.init();
  scanf("%d",&l);
  for (ri i=1;i<=l;i++) scanf("%d",&a[i]);
  for (ri i=1;i<=l;i++) sam.extend(a[i]);
  for (ri i=1;i<=l;i++) sam.extend(a[i]);
  int now=1;
  for (ri i=1;i<=l;i++) {
    printf("%d ",t[now].ch.begin()->first);
    now=t[now].ch.begin()->second;
  }
}