【题解】Puzzle [Uva1399]

【题目描述】

给定 \(m\) 和 \(n\)，表示有 \(m\) 种不同的字符（大写字母\(A,B,C \cdots\)），\(n\) 个禁止串，请构造一个不包含任何禁止串的最长字符串并将其输出。如果可以无限长或者无解则输出 \(No\)，如果存在多解则输出字典序最大的一种。

【输入】

第一行一个整数T表示数据组数。

接下来每组数据第一行为两个整数 \(m,n\)，接下来 \(n\) 行输入 \(n\) 个禁止串。

【输出】

一行表示答案。

【样例】

样例输入：
3
2 4
AAA
AB
BA
BB
2 4
AAA
BBB
ABAB
BBAA
3 7
AA
ABA
BAC
BB
BC
CA
CC

样例输出：
AA
No
ACBAB

【数据范围】

\(100\%:\) \(1 \leqslant m \leqslant 26,\) \(1 \leqslant n \leqslant 1000\)

【分析】

\(AC\) 自动机 \(+\) \(dp\) 的裸题。

按照套路，先对 \(n\) 个禁止串建立 \(AC\) 自动机，在每个禁止串的结尾节点处打个 \(end\) 标记，然后利用 \(fail\) 树向上传递标记。

用 \(dp[x]\) 表示从 \(AC\) 自动机上节点 \(x\) 开始往下不经过禁止串结尾标记所能延伸的最大长度，则有 \(dp[x]=max\{dp[tr[x][ch]]+1\}\) \((ch \in[0,m-1])\) 。

从根节点开始 \(dfs\)，用 \(vis[x]\) 记录 \(x\) 节点是否在当前扫描出来的路径上，如果 \(vis[x]=1\)，则说明在 \(AC\) 自动机上出现了合法的循环，如果一直沿着这个循环延伸下去，就可以构造出无限长的合法串。

为了防止超时，还需要记忆化，用 \(pan[x]\) 记录 \(x\) 节点是否已经搜过（注意 \(vis\) 和 \(pan\) 判断的先后顺序）。

至于输出答案，在 \(dp\) 转移时用一个辅助数组 \(g\) 记录最优决策点即可。

另外，这题有个简化版（只需要判断是否可以无限长）：病毒 \(\text{[POI2000] [P2444]}\)

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,M=5e4+3;
int n,C,T;char ch[53];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct AC_Automaton{
    int O,g[M],ed[M],dp[M],vis[N],pan[M],fail[M],tr[M][26];queue<int>Q;
    inline void CL(){
        memset(fail,0,sizeof(fail));
        memset(pan,0,sizeof(pan));
        memset(vis,0,sizeof(vis));
        memset(tr,0,sizeof(tr));
        memset(ed,0,sizeof(ed));
        memset(dp,0,sizeof(dp));
        memset(g,-1,sizeof(g));
        O=1;
    }
    inline void insert(char ch[]){
        Re p=1;
        for(Re i=1;ch[i];++i){
            Re a=ch[i]-'A';//注意是大写A
            if(!tr[p][a])tr[p][a]=++O;
            p=tr[p][a];
        }
        ed[p]=1;
    }
    inline void get_fail(){
        for(Re i=0;i<C;++i)tr[0][i]=1;
        Q.push(1);
        while(!Q.empty()){
            Re x=Q.front();Q.pop();
            for(Re i=0;i<C;++i)
                if(tr[x][i])fail[tr[x][i]]=tr[fail[x]][i],Q.push(tr[x][i]);
                else tr[x][i]=tr[fail[x]][i];
            ed[x]|=ed[fail[x]];
        }
    }
    inline int dfs(Re x){
        if(vis[x])return 1;//在正在搜的路径中出现过x，即出现循环
        if(pan[x])return 0;//已经搜过x了，肯定无果
        vis[x]=pan[x]=1;
        for(Re i=C-1,to;i>=0;--i)//注意求字典序最大
            if(!ed[to=tr[x][i]]){
                if(dfs(to))return 1;
                if(dp[to]+1>dp[x])dp[x]=dp[to]+1,g[x]=i;
            }
        vis[x]=0;//搜过x后要换成fa[x]的另一条分支往下延伸，所以要还原成0
        return 0;
    }
    inline void sakura(){
        if(dfs(1))puts("No");//无限长
        else{
            Re ans=0;
            for(Re i=1;i<=O;++i)if(dp[i]>dp[ans])ans=i;
            if(!ans)puts("No");//无解
            else{
                Re p=1;
                while(g[p]!=-1){
                    printf("%c",'A'+g[p]);
                    p=tr[p][g[p]];
                }
                puts("");
            }
        }
    }
}AC;
int main(){
//  freopen("123.txt","r",stdin);
    in(T);
    while(T--){
        in(C),in(n),AC.CL();
        while(n--)scanf("%s",ch+1),AC.insert(ch);
        AC.get_fail(),AC.sakura();
    }
}