自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 23:16:26，当前版本为作者最后更新于2025-05-20 11:06:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

记 $s[l,r]$ 表示字符串 $s$ 下标在范围 $[l,r]$ 内的子串。下文中字符串下标全部从 $0$ 开始。

考虑 $q=0$ 怎么做，显然现在每个点上面的字符已经确定了，于是只需要找后继。由于给出的字符串长度为 $3n$，所以一个点 $u$ 的后继 $p_u$ 必然满足 $s_u[1,3n-1]=s_{p_u}[0,3n-2]$。直接对于每个 $u$ 暴力枚举 $p_u$，用字符串哈希判等，即可通过 $q=0$ 的 $63$ 分。

那么如何扩展到正解？注意到正解比 $q=0$ 多出来的东西是一些字符串未知的结点，沿用上面的方法，如果某一个点 $u$ 没找到后继，那么直接将后继设为某个字符串未知的结点 $v$；显然可以通过这样的方式确定整个 $s_v$——具体地可以发现 $s_v$ 相当于 $s_u$ 删掉首字母再在末尾加上一个字母，而 $s_u$ 的长度为 $3n$ 所以可以直接枚举基环树上环的长度（用哈希判断这个长度是否合法），进而可以唯一确定 $s_v$ 的最后一位；之后再递归下去给 $s_v$ 找后继……题目保证有解，所以这样的操作过程是正确的。

枚举长度并判定循环的部分是经典调和级数时间复杂度，而我们要对于每个找不到后继的字符串都做一遍，所以总的时间复杂度为 $O(n^2\log n)$，常数非常小可以通过。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int B=6907,P=1e9+9;
class hashing{
  private:
    vector<int> p,h;
  public:
    hashing(string a){
      p.resize(a.size()+1),h.resize(a.size());
      for(int i=p[0]=1;i<=a.size();i++)
        p[i]=1ll*p[i-1]*B%P;
      for(int i=0;i<a.size();i++)
        h[i]=(1ll*(i?h[i-1]:0)*B+a[i]-96)%P;
    }
    inline int get(int l,int r){
      return (h[r]-(l?1ll*h[l-1]*p[r-l+1]%P:0)+P)%P;
    }
}; // 字符串哈希模板
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin>>n;
  vector<string> s(n);
  vector<int> v;
  for(auto &i:s)cin>>i;
  vector<optional<hashing> > h(n);
  for(int i=0;i<n;i++){
    h[i].emplace(s[i]);
    if(s[i][0]=='?')v.emplace_back(i);
  } // 预处理一些信息
  vector<int> p(n,-1);
  auto gen=[&](int x,int y){
    auto t=s[x].substr(1,n*3-1);
    for(int l=1;l<=n;l++){
      bool f=true;
      for(int j=n*3-l;j>=n&&f;j-=l)
        f&=h[x]->get(j,j+l-1)==h[x]->get(n*3-l,n*3-1);
      if(f){t+=s[x][n*3-l]; break;}
    }
    return t;
  }; // 通过 s[x] 生成 s[y]，即删一个字母加一个字母的过程
  auto dfs=[&](auto &&self,int x)->int{
    for(int i=0;i<n;i++)
      if(s[i][0]!='?'&&h[x]->get(1,n*3-1)==h[i]->get(0,n*3-2))return i;
    int y=v.back(); v.pop_back(); // 没找到，取一个字符串未知的
    return h[y].emplace(s[y]=gen(x,y)),p[y]=self(self,y),y;
  }; // 找后继
  for(int i=0;i<n;i++)
    if(s[i][0]!='?')p[i]=dfs(dfs,i);
  for(int i=0;i<n;i++)
    if(p[i]<0)s[i][0]='q',p[i]=i; // 剩下的未确定的随便填
  for(int i=0;i<n;i++)
    cout<<s[i][0];
  cout<<endl;
  for(int i:p)cout<<i+1<<' ';
  cout<<endl;
  return 0;
}