思路

\(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;

}

巴特西

luogu1368 工艺

思路

代码

最新文章

热门文章