退役选手复活后的第一篇。
https://www.luogu.com.cn/problem/SP4033
其实只要一个 insert.
就是插入时没新建节点 \(\to\) 自己是别人前缀，
插入时途经了别人的结束节点 \(\to\) 别人是自己前缀。
code
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=31;
int n,cnt,in[M];
int tot,trie[N][M];
vector<int> G[M];
string s[N],ans[N];
bool vis[N];
void insert(string s){
int cur=0;
for(int i=0;i<s.size();i++){
if(!trie[cur][s[i]-'a'])
trie[cur][s[i]-'a']=++tot;
cur=trie[cur][s[i]-'a'];
}
vis[cur]=1; return;
}
bool build(string s){
int cur=0;
for(int i=0;i<s.size();i++){
if(vis[cur]) return 0;
for(int j=0;j<26;j++)
if((int)(s[i]-'a')!=j&&trie[cur][j])
G[s[i]-'a'].push_back(j),in[j]++;
cur=trie[cur][s[i]-'a'];
}
return 1;
}
bool topo(){
queue<int> q; int res=0;
for(int i=0;i<26;i++)
if(!in[i]) q.push(i);
while(!q.empty()){
int cur=q.front();
q.pop(),res++;
for(int i:G[cur]){
in[i]--;
if(!in[i]) q.push(i);
}
}
return res==26;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i],insert(s[i]);
for(int i=1;i<=n;i++){
for(int i=0;i<M;i++) G[i].clear();
memset(in,0,sizeof(in));
if(build(s[i])&&topo()) ans[++cnt]=s[i];
}
cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++) cout<<ans[i]<<'\n';
return 0;
}
https://www.luogu.com.cn/problem/P3065
bf 是全排列字典然后依照他去 sort.
考虑转换问题思考角度，尝试将每个字符串作为第一个。
探索性质：
-
若一个字符串是别人的前缀，则他永远也成不了第一个
-
若一个字符串是第一个，则他向 trie 中与它同层的节点连边，一定不会出现矛盾（即出现环）
第一条很好理解，而第二条实际是说连边后形成的图为 DAG（有拓扑序），这个拓扑序就是满足当前字符串为第一个的字典顺序。
于是我们连边跑 toposort / tarjan 判环即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=31;
int n,cnt,in[M];
int tot,trie[N][M];
vector<int> G[M];
string s[N],ans[N];
bool vis[N];
void insert(string s){
int cur=0;
for(int i=0;i<s.size();i++){
if(!trie[cur][s[i]-'a'])
trie[cur][s[i]-'a']=++tot;
cur=trie[cur][s[i]-'a'];
}
vis[cur]=1; return;
}
bool build(string s){
int cur=0;
for(int i=0;i<s.size();i++){
if(vis[cur]) return 0;
for(int j=0;j<26;j++)
if((int)(s[i]-'a')!=j&&trie[cur][j])
G[s[i]-'a'].push_back(j),in[j]++;
cur=trie[cur][s[i]-'a'];
}
return 1;
}
bool topo(){
queue<int> q; int res=0;
for(int i=0;i<26;i++)
if(!in[i]) q.push(i);
while(!q.empty()){
int cur=q.front();
q.pop(),res++;
for(int i:G[cur]){
in[i]--;
if(!in[i]) q.push(i);
}
}
return res==26;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i],insert(s[i]);
for(int i=1;i<=n;i++){
for(int i=0;i<M;i++) G[i].clear();
memset(in,0,sizeof(in));
if(build(s[i])&&topo()) ans[++cnt]=s[i];
}
cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++) cout<<ans[i]<<'\n';
return 0;
}
https://www.luogu.com.cn/problem/P4407
考虑一种很 bf 的方法：在 trie 上 dfs。但是她能过。
添加 \(\to\) 原串跳一个字符，询问串不动。
删除 \(\to\) 原串不动，询问串跳一个字符。
替换 \(\to\) 原串、询问串各自跳一个字符。
具体细节见代码。
code
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=31;
int n,m;
int tot,trie[N][M];
int tagtot,tagx[N];
bool isword,tag[N],vis[N];
void insert(string s){
int cur=0;
for(int i=0;i<s.size();i++){
if(!trie[cur][s[i]-'a'])
trie[cur][s[i]-'a']=++tot;
cur=trie[cur][s[i]-'a'];
}
vis[cur]=1; return;
}
void search(string s,int cur,int len,bool flag){
if(len==s.size()&&vis[cur]&&flag){ isword=1; return; }
if(len==s.size()&&vis[cur]&&!flag){
if(!tag[cur])
tag[tagx[++tagtot]=cur]=1;
return;
}
if(flag){
if(len<s.size()) search(s,cur,len+1,!flag);
for(int i=0;i<26;i++){
if(trie[cur][i]){
search(s,trie[cur][i],len,!flag);
if(i!=(int)(s[len]-'a'))
search(s,trie[cur][i],len+1,!flag);
}
}
}
if(trie[cur][s[len]-'a'])
search(s,trie[cur][s[len]-'a'],len+1,flag);
if(len>=s.size()) return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
string w;
cin>>w,insert(w);
}
for(int i=1;i<=m;i++){
string q; cin>>q;
for(int j=1;j<=tagtot;j++)
tag[tagx[j]]=0,tagx[j]=0;
tagtot=0,isword=0;
search(q,0,0,1);
if(isword) cout<<"-1\n";
else cout<<tagtot<<'\n';
}
return 0;
}
https://www.luogu.com.cn/problem/P4683
又是上题的套路。
考虑一种贪心：把最长的留在最后打印，这样删除字符数更少。显然（？）这是正确的。
于是我们遇到最长的就在 trie 上标记一遍，dfs 时没标记的先跑即可。
在 trie 上 dfs 就保证了前缀不会重复删去又加上。
以后看到要输出方案都可以考虑 dfs。
code
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,M=26;
int m,cnt;
string ans,s[25005];
int tot,trie[N][M];
bool vis[N],mk[N];
char ch[N];
void insert(string ss){
int cur=0;
for(int i=0;i<ss.size();i++){
if(!trie[cur][ss[i]-'a'])
trie[cur][ss[i]-'a']=++tot;
cur=trie[cur][ss[i]-'a'];
ch[cur]=ss[i];
}
vis[cur]=1;
}
void mark(string ss){
int cur=0;
for(int i=0;i<ss.size();i++){
cur=trie[cur][ss[i]-'a'];
mk[cur]=1;
}
}
void search(int cur){
if(vis[cur]) cnt++,ans+="P";
if(cnt==m){
cout<<ans.size()<<'\n';
for(int i=0;i<ans.size();i++) cout<<ans[i]<<'\n';
}
for(int i=0;i<26;i++){
if(trie[cur][i]&&!mk[trie[cur][i]]){
ans+=ch[trie[cur][i]];
search(trie[cur][i]);
ans+="-";
}
}
for(int i=0;i<26;i++){
if(trie[cur][i]&&mk[trie[cur][i]]){
ans+=ch[trie[cur][i]];
search(trie[cur][i]);
ans+="-";
}
}
}
int main(){
cin>>m;
int maxz=0,pos=0;
for(int i=1;i<=m;i++){
cin>>s[i];
if(s[i].size()>maxz)
maxz=s[i].size(),pos=i;
}
for(int i=1;i<=m;i++){
insert(s[i]);
if(pos==i) mark(s[i]);
}
search(0);
return 0;
}