csp模拟<反思>3
csp模拟21
ARC141F
首先上结论：如果一个串能用其他串消完那么这个串可以删去；
剩下的串中有 \(S_i\) 是 \(S_j\) 的子串，那么答案是 Yes;
如果存在 \(S_i=A+B\) 和 \(S_j=B+C\)，且 \(A \neq C\) 则答案是 Yes.
第一部分：如何判断一个串 \(S_i\) 是否能被消完。
建 AC 自动机，预处理 \(mark\) 表示其点 fail 树祖先上的某一个终止节点。开一个栈，栈里存在树上的编号，每压入一个点，从这个点跳 \(mark\) 匹配到终止节点，在栈中删去串的长度。匹配到最后如果栈中没元素，则此串可以删去，如果有元素且小于原始长度,则答案 Yes。
第二部分，对筛选出来的串在 AC自动机里跑一边，记录每个点被经历的次数和被谁经历。如果经历次数大于 1,则答案为 Yes。
设 \(f_{i,t}(t\le len_i)\)表示 \(S_i\) 长为 \(t\) 的后缀，可以匹配到的某一个 \(S_j\) 的前缀。可以对每个串跳 \(fail\) 求出。
接着对于每个 \(j=f_{i,t}\)，只要存在 \(len_i \neq len_j\) 或 \(f_{j,len_{i-t}}==i\) 那么这就是坏串，则答案为 \(Yes\)。
不为 Yes 则为 No。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2*1e6+10;
string s[N];
int tr[N][4],tot=0,fail[N],en[N],len[N],rk[N],d[N],idx[N],pk[N];
map<int,int>f[N];
int b[N];
bool vis[N];
int st[N],top;
int head[N],nex[N],ver[N],tot_node=0,mark[N][2];
queue<int> q;
void add(int x,int y){
ver[++tot_node]=y;nex[tot_node]=head[x],head[x]=tot_node;
}
void insert(string s1,int id){
int u=0;
for(int i=0;s1[i];i++){
int ch=s1[i]-'A';
if(!tr[u][ch]) tr[u][ch]=++tot;
d[tr[u][ch]]=d[u]+1;
u=tr[u][ch];
}
en[u]++;
rk[id]=u;
}
void build(){
for(int i=0;i<4;i++){
if(tr[0][i]){
add(0,tr[0][i]);
q.push(tr[0][i]);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<4;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
add(fail[tr[u][i]],tr[u][i]);
q.push(tr[u][i]);
}
else{
tr[u][i]=tr[fail[u]][i];
}
}
}
}
void dfs(int x,int f){
mark[x][0]=mark[f][0];
if(en[x]){
mark[x][0]=x;
mark[x][1]=mark[f][0];
}
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(y==f) continue;
dfs(y,x);
}
}
void ask(string s1,int id){
int u=0;
for(int i=0;s1[i];i++){
int ch=s1[i]-'A';
u=tr[u][ch];
pk[u]=id;
idx[u]++;
}
}
void clear(int x){
tot=0,tot_node=0;
memset(tr,0,sizeof(tr));
memset(fail,0,sizeof(fail));
memset(mark,0,sizeof(mark));
memset(en,0,sizeof(en));
memset(len,0,sizeof(len));
memset(rk,0,sizeof(rk));
memset(d,0,sizeof(d));
memset(idx,0,sizeof(idx));
memset(pk,0,sizeof(pk));
memset(head,0,sizeof(head));
memset(nex,0,sizeof(nex));
memset(ver,0,sizeof(ver));
memset(vis,0,sizeof(vis));
for(int i=1;i<=x;i++){
f[i].clear();
}
}
int main(){
int T=1;
while(T--){
int n;
scanf("%d",&n);
clear(n);
for(int i=1;i<=n;i++){
cin>>s[i];
len[i]=s[i].size();
insert(s[i],i);
}
build();
dfs(0,0);
int getans=0;
for(int k=1;k<=n;k++){
int u=0;
top=0;
for(int i=0;i<len[k];i++){
u=tr[st[top]][s[k][i]-'A'];
st[++top]=u;
if(rk[k]!=u && mark[u][0]) top-=d[mark[u][0]];
if(rk[k]==u && mark[u][1]) top-=d[mark[u][1]];
}
if(top==0) vis[k]=1;
if(top && top<len[k]){
printf("Yes\n");
getans=1;
break;
}
}
if(getans) continue;
for(int i=1;i<=n;i++){
if(vis[i]) continue;
ask(s[i],i);
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
int tmp=rk[i];
int last=0;
while(fail[tmp]){
tmp=fail[tmp];
if(last==d[tmp]){
printf("Yes\n");
getans=1;
break;
}
f[i][d[tmp]]=pk[tmp];
last=d[tmp];
}
if(getans) break;
}
if(getans) continue;
for(int i=1;i<=n;i++){
if(vis[i]) continue;
int tmp=rk[i];
while(fail[tmp]){
tmp=fail[tmp];
int t=d[tmp];
int j=f[i][t];
if(!j) continue;
if(len[i]!=len[j] ||f[j][len[i]-t]!=i){
printf("Yes\n");
getans=1;
break;
}
}
if(getans) break;
}
if(getans) continue;
printf("No\n");
}
}