题解：P12553 [UOI 2024] Lady's Gift

· · 题解

感觉比较有意思的一道所谓构造题。

考虑整个东西构成一个基环树森林，所以每个串最后都会走到环上，在串的一个后缀形成周期。

显然我们截取 [n+1,3n] 的后缀来判定周期就足够了。对于每个串，这个后缀的周期都有可能是它所在连通块环的样子。

考虑如下两个性质：

所以我们只需找出最小周期就能把串分到自己的连通块里。直接枚举最小周期在 [n+1,3n] 占据了多长的前缀并使用哈希判定即可做到 \mathcal O(n^2\ln n)。

然后考虑我们需要将最小周期循环同构的串塞到一起。这也可以使用哈希，对于每个新出现的周期，将它的所有循环同构串的哈希全部搞出来打上标记就可以了。

现在我们知道了每个串的起点所在的连通块和对应连通块环的形态。考虑我们显然希望一个串有尽可能长的后缀是在环上的，非要留出一段可以在环上的作为支链显然不优。

所以我们可以先对每个串找出第一个不能够在环上的位置，把剩余那个前缀挂在最后一个在环上的点上（当然如果整个串都在环上就直接挂在最后一个点上）。而由于这个串的每个后缀都必须找到对应走法的串，所以实际上我们是挂了一颗内向的字典树上去，字典树的每个节点都必须有至少一个串的起点对应到。

现在每个连通块形如一个基环字典树，我们的目标是所有节点上都有一个串的起点对应。据此我们可以分配掉未知的串，显然我们的构造是需要的数量的下界。

然后考虑如何构造方案。显然每个串的起点的字符就是它对应的点在字典树上表示的字符（或者，它父亲到它边上的字符）；而每个串起点的点的指向可以考虑，所在的点在字典树上的部分显然是内向的，而环上的部分只需要和刚刚从环上退，找到第一个不在环上的位置的时候方向相同就可以了。

如果还有多出来的未知的串，自环即可。

时间复杂度 \mathcal O(n^2\ln n)。我的写法好像比较暴力。

const int base=293;
const int mod1=200707201,mod2=998244353;
int bm1[N*3],bm2[N*3];
struct Hashing{
    int val1,val2,len;
    Hashing operator+(const Hashing p)const{
        return {(1ll*val1*bm1[p.len]%mod1+p.val1)%mod1,
                (1ll*val2*bm2[p.len]%mod2+p.val2)%mod2,
                len+p.len
        };
    }
    Hashing operator-(const Hashing p)const{//cut prefix out
        return {(val1+mod1-1ll*p.val1*bm1[len-p.len]%mod1)%mod1,
                (val2+mod2-1ll*p.val2*bm2[len-p.len]%mod2)%mod2,
                len-p.len
        };
    }
    bool operator==(const Hashing p)const{
        return val1==p.val1&&val2==p.val2&&len==p.len;
    }
    bool operator<(const Hashing p)const{
        if(val1==p.val1){
            if(val2==p.val2) return len<p.len;
            return val2<p.val2;
        }
        return val1<p.val1;
    }
    bool operator!=(const Hashing p)const{
        return !((*this)==p);
    }
};
int n;
string s[N];
Hashing pre[N*3];
string pat[N];
map <Hashing,pii> p;
vector <pii> trie[N][N];
vector <int> q;
int c[N],bol[N];
char tp[N],ans[N];
int r[N];
vector <int> cho[N];
int nxt[N];
int tot,ch[N][26];
int main(){
#ifdef Shun
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    bm1[0]=bm2[0]=1;
    fr1(i,1,6000) bm1[i]=1ll*bm1[i-1]*base%mod1,bm2[i]=1ll*bm2[i-1]*base%mod2;
    cin>>n;
    fr1(i,1,n) cin>>s[i],s[i]='@'+s[i];
    fr1(i,1,n){
        if(s[i][1]=='?'){
            q.pb(i);
            continue;
        }
        int cir=-1;
        pre[0]={0,0,0};
        fr1(j,1,3*n) pre[j]=pre[j-1]+(Hashing){s[i][j],s[i][j],1};
        fr1(j,1,n){
            for(int l=n+1;l<=n+n;l+=j){
                if(pre[l+j-1]-pre[l-1]!=pre[n+j]-pre[n]) goto label;
            }
            cir=j;
            break;
            label:;
        }
        assert(~cir);
        c[i]=cir;
        Hashing lp={0,0,0};
        fr1(j,n+1,n+cir) lp=lp+(Hashing){s[i][j],s[i][j],1};
        fr1(j,n+1,n+cir){
            if(p.count(lp)){
                c[i]=0;
                continue;
            }
            p[lp]={i,j-n};
            lp=lp+(Hashing){s[i][j],s[i][j],1}-(Hashing){s[i][j],s[i][j],1};
        }
        int pos=p[lp].se;
        fr2(j,n,1){
            if(s[i][j]==s[i][j+cir]){
                pos--;
                if(!pos) pos=cir;
                continue;
            }
            trie[p[lp].fi][pos].pb(mp(i,j));
            goto label2;
        }
        trie[p[lp].fi][pos].pb(mp(i,0));
        label2:;
    }
    fr1(i,1,n){
        int maxn=0;
        fr1(j,1,tot){
            cho[j].clear();
            fr1(k,0,25) ch[j][k]=0;
        }
        tot=c[i];
        fr1(j,1,c[i]){
            nxt[j]=j%c[i]+1;
            tp[j]=s[i][n+j];
            for(auto k:trie[i][j]){
                string t=s[k.fi].substr(1,k.se);
                reverse(t.begin(),t.end());
                int pos=j;
                for(auto p:t){
                    if(!ch[pos][p-'a']){
                        tot++;
                        tp[tot]=p;
                        ch[pos][p-'a']=tot;
                        nxt[tot]=pos;
                    }
                    pos=ch[pos][p-'a'];
                }
                cho[pos].pb(k.fi);
            }
        }
        fr1(j,1,tot){
            if(cho[j].empty()){
                assert(!q.empty());
                cho[j].pb(q.back());
                q.pop_back();
            }
        }
        fr1(j,1,tot){
            for(auto k:cho[j]){
                ans[k]=tp[j];
                r[k]=cho[nxt[j]].back();
            }
        }
    }
    while(!q.empty()){
        ans[q.back()]='z',r[q.back()]=q.back();
        q.pop_back();
    }
    fr1(i,1,n) cout<<ans[i];
    cout<<'\n';
    fr1(i,1,n) cout<<r[i]<<' ';
    ET;
}
//ALL FOR Zhang Junhao.