题目链接
Solution
感觉比较巧的题啊...
考虑几点:
- 可以交换无数次字母表,即字母表可以为任意形态.
- 对于以其他字符串为前缀的字符串,我们可以直接舍去.
因为此时它所包含的前缀的字典序绝对比它本身小. 需要使得某个字符串 \(S\) 字典序最小,需要讨论两种情况:
\(1.\) 与它没有公共前缀的字符串
此时我们即使得 \(S_{1}\) 大于其第一个即可.\(2.\) 与它有公共前缀的字符串
我们令其最长公共前缀的位置为 \(k\) .
那么此时我们即要求,对于任意字符串 \(T\), 在字母表中 \(S_{k+1}<T_{k+1}\) .
我们可以将这种关系在 \(26\) 个字母中形成一张关系图,判断是否满足条件.
直接判环即可.
其实以上两种情况可以都理解为第二种情况,只是第一种情况的\(k=0\)罢了.
怎样去快速定位公共前后缀的位置?
我们使用 \(Trie\) 树,直接将所有字符串插入 \(Trie\) 树中.
每一次处理都对当前节点所有的非本字符串节点连边,然后拓扑排序判环即可.
总时间复杂度 \(O(sum_{len}*26)\)
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=300008;
int ch[maxn][26];
int num[maxn],n,cnt;
struct sj{int to;int next;
}a[1008];
int du[30],tot,fuck;
int head[30],size;
string ans[maxn];void add(int x,int y)
{a[++size].to=y;a[size].next=head[x];head[x]=size;
}void dfs()
{queue<int>q;for(int i=0;i<26;i++)if(!du[i])q.push(i);while(!q.empty()){int now=q.front();q.pop();for(int i=head[now];i;i=a[i].next){int tt=a[i].to;du[tt]--;if(!du[tt])q.push(tt);}}
}int insert(char *s)
{int len=strlen(s),u=0;for(int i=0;i<len;i++){if(!ch[u][s[i]-'a'])ch[u][s[i]-'a']=++tot;if(num[ch[u][s[i]-'a']])return 1;u=ch[u][s[i]-'a'];}num[u]++;return 0;
}int pre(string s)
{int len=s.length(),u=0;for(int i=0;i<len;i++){int p=s[i]-'a';for(int j=0;j<26;j++){if(ch[u][j]!=0&&j!=p)add(p,j),du[j]++;}u=ch[u][p];if(i!=len-1&&num[u]!=0)return 0;}return 1;
}
string s[maxn];
char cha[maxn];
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){ scanf("%s",cha);if(!insert(cha)){cnt++;int len=strlen(cha);for(int j=0;j<len;j++)s[cnt]+=cha[j];}}for(int i=1;i<=cnt;i++){memset(a,0,sizeof(a)),size=0;memset(head,0,sizeof(head));memset(du,0,sizeof(du));if(!pre(s[i])){continue;}dfs();int flag=1;for(int j=0;j<26;j++)if(du[j])flag=0;if(flag)ans[++fuck]=s[i];}cout<<fuck<<endl;for(int i=1;i<=fuck;i++)cout<<ans[i]<<endl;
}
P3065 [USACO12DEC]第一!First!