bzoj 1398: 寻找主人 AC自动机+最小表示法

题目大意:

给定两个序列判断是否循环同构,若循环同构则输出最小表示

题解:

因为没有样例输入输出,一开始没看到要求输出最小表示

Wa一大页.

但不得不说bzoj还是挺高效的:

赞一个 XD.jpg

判断是否循环同构用kmp即可,可惜本人并不会kmp,用的AC自动机.

然后去学了一发求最小表示法方法...这。。。貌似是模板题..

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch = getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 1100010;

int ch[maxn][11],fail[maxn];

bool danger[maxn];

int nodecnt = 0;

char s[maxn<<1];

inline void insert(){

	int nw = 0,len = strlen(s);

	for(int i=0,c;i<len;++i){

		c = s[i] - '0';

		if(ch[nw][c] == 0) ch[nw][c] = ++ nodecnt;

		nw = ch[nw][c];

	}danger[nw] = true;

}

int q[maxn],l,r;

inline void build(){

	l = 0;r = -1;fail[0] = 0;

	for(int i=0;i<=9;++i){

		if(ch[0][i]){

			fail[ch[0][i]] = 0;

			q[++r] = ch[0][i];

		}

	}

	while(l <= r){

		int u = q[l++];

		for(int i=0;i<=9;++i){

			int t = ch[fail[u]][i];

			if(ch[u][i] == 0) ch[u][i] = t;

			else{

				danger[ch[u][i]] |= danger[t];

				fail[ch[u][i]] = t;

				q[++r] = ch[u][i];

			}

		}

	}

}

inline bool find(){

	int nw = 0,len = strlen(s);

	for(int i=0;i<len;++i){

		nw = ch[nw][s[i] - '0'];

		if(danger[nw]) return true;

	}return false;

}

inline int find2(){

	int i=0,j=1,k=0,len = strlen(s);

	while(i < len && j < len){

		for(k = 0;s[(i+k)%len] == s[(j+k)%len] && k < len;++k);

		if(k == len) return i;

		if(s[(i+k)%len] > s[(j+k)%len]) i = max(i+k+1,j+1);

		else j = max(j+k+1,i+1);

	}

	if(i < len) return i;

	else return j;

}

int main(){

	scanf("%s",s);insert();build();

	scanf("%s",s);int n = strlen(s);

	for(int i=0;i<n;++i) s[n+i] = s[i];

	if(find()){

		puts("Yes");

		s[n] = 0;

		int i = find2();

		for(int j=0;j<n;++j) putchar(s[(i+j)%n]);

	}else puts("No");

	getchar();getchar();

	return 0;

}

巴特西

bzoj 1398: 寻找主人 AC自动机+最小表示法

题目大意:

题解:

最新文章

热门文章