「题解」字符串

本文主要是介绍「题解」字符串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本文将同步发布于：

• 洛谷博客；
• csdn；
• 博客园；
• 简书。

题目

题目描述

给出一个长度为 \(n\) 的只包含 \(\texttt{a}\) 到 \(\texttt{l}\) 的小写字符串。你可以选择一个 \(\texttt{a}\) 至 \(\texttt{l}\) 的排列 \(p_a,\cdots,p_l\)，然后令 \(t=p_{s_1}\cdots p_{s_n}\)，你需要对每一个 \(i\in[1,n]\) 判断是否存在一个排列 \(p\)，满足 \(t\) 中以 \(i\) 为开头的后缀是字典序最大的后缀。

数据组数 \(\leq 10^3\)，\(n\leq 10^5\)。

题解

简单又自然

我们不妨想到一个简单的暴力。

我们建立一棵 Trie 树，将所有的后缀插入 Trie 树。

如果一个后缀 \(u\) 满足其字典序最大，那么根到其路径上的每个字母都是最大的转移，我们建立一个图，判定是否有环即可。

Trie 的压缩

Trie 里面存储了所有的后缀，因此，其实这个 Trie 的压缩就是原串的后缀树，我们直接用后缀自动机建立后缀树即可。

参考程序

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

bool st;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?exit(0),EOF:*p1++)
static char buf[1<<21],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) res=10*res+(ch^'0'),ch=getchar();
	return res;
}

inline char* read(reg char *s){
	*s=getchar();
	while(!isalpha(*s)) *s=getchar();
	while(isalpha(*s)) *(++s)=getchar();
	*s='\0';
	return s;
}

const int MAXN=1e5+5;
const int lim=12;

namespace ST{
	struct Node{
		int fa,dep,id;
		int ch[lim];
		#define fa(x) unit[(x)].fa
		#define dep(x) unit[(x)].dep
		#define ch(x) unit[(x)].ch
		#define id(x) unit[(x)].id
	};
	int tot,las;
	Node unit[MAXN<<1];
	inline int getId(void){
		reg int p=++tot;
		memset(&unit[p],0,sizeof(unit[p]));
		return p;
	}
	inline void init(void){
		tot=0;
		las=getId();
		return;
	}
	inline void insert(reg int c,reg int Id){
		reg int p=las,np=getId();
		dep(np)=dep(p)+1,id(np)=Id;
		while(p&&!ch(p)[c])
			ch(p)[c]=np,p=fa(p);
		if(!p)
			fa(np)=1;
		else{
			reg int q=ch(p)[c];
			if(dep(q)==dep(p)+1)
				fa(np)=q;
			else{
				reg int nq=getId();
				dep(nq)=dep(p)+1;
				memcpy(ch(nq),ch(q),sizeof(ch(q)));
				fa(nq)=fa(q),fa(q)=fa(np)=nq;
				while(ch(p)[c]==q)
					ch(p)[c]=nq,p=fa(p);
			}
		}
		las=np;
		return;
	}
	vector<int> G[MAXN<<1];
	inline void build(void){
		for(reg int i=1;i<=tot;++i)
			G[i].clear();
		for(int i=2;i<=tot;++i)
			G[fa(i)].push_back(i);
		return;
	}
	inline void dfs(reg int u){
		for(int v:G[u]){
			dfs(v);
			id(u)=id(v);
		}
		return;
	}
}

int n;
char s[MAXN];
char ans[MAXN];
int cnt[lim][lim];

namespace Graph{
	int inDeg[lim];
	vector<int> G[lim];
	inline bool check(void){
		for(reg int i=0;i<lim;++i)
			inDeg[i]=0,G[i].clear();
		for(reg int i=0;i<lim;++i)
			for(int j=0;j<lim;++j)
				if(cnt[i][j])
					G[i].push_back(j),++inDeg[j];
		reg int _head=0,_tail=0;
		static int Q[lim];
		for(reg int i=0;i<lim;++i)
			if(!inDeg[i])
				Q[_tail++]=i;
		reg int cnt=0;
		while(_head<_tail){
			reg int u=Q[_head++];
			++cnt;
			for(int v:G[u]){
				--inDeg[v];
				if(!inDeg[v])
					Q[_tail++]=v;
			}
		}
		return cnt<lim;
	}
}

inline void dfs(reg int u){
	if(ST::G[u].empty()){
		if(!Graph::check())
			ans[ST::id(u)]=1;
		return;
	}
	for(int v1:ST::G[u]){
		reg int c1=s[ST::dep(u)+ST::id(v1)];
		for(int v2:ST::G[u])
			if(v1!=v2){
				reg int c2=s[ST::dep(u)+ST::id(v2)];
				++cnt[c1][c2];
			}
		dfs(v1);
		for(int v2:ST::G[u])
			if(v1!=v2){
				reg int c2=s[ST::dep(u)+ST::id(v2)];
				--cnt[c1][c2];
			}
	}
	return;
}

bool ed;

int main(void){
	reg int t=read();
	while(t--){
		n=read(s)-s;
		for(reg int i=0;i<n;++i)
			s[i]-='a';
		ST::init();
		for(reg int i=n-1;i>=0;--i)
			ST::insert(s[i],i);
		ST::build();
		ST::dfs(1);
		dfs(1);
		for(reg int i=0;i<n;++i)
			putchar(ans[i]+'0'),ans[i]=0;
		putchar('\n');
	}
	fprintf(stderr,"%.3lf s\n",1.0*clock()/CLOCKS_PER_SEC);
	fprintf(stderr,"%.3lf MiB\n",(&ed-&st)/1048576.0);
	return 0;
}

这篇关于「题解」字符串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！