题解：P11941 [CrCPC 2024] 牙牙学语

· · 题解

普通哈希，直接哈希套搜索（广搜）即可。
题意可简化为使用这些字符串用两种不同拼法拼成相同的字符串。
搜索时，我们可以选取拼出的较短序列，比较哈希值，枚举可行字符串入队，这样，只需在队列里存储较长序列中末尾字符串的编号，以及未被匹配的节点。
代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,x[11451410],x1=233,p1=998244353,l[30],v[11451410],k[30];
string s[30];
vector<int>a[114514];
struct N{int a,b;};
queue<N>p;
int bfs()
{
    while(p.size())
    {
        N t=p.front();p.pop();
        if(t.b==l[t.a])return 1;
        if(v[k[t.a-1]+t.b])continue;//搜过
        v[k[t.a-1]+t.b]=1;
        for(int i=1;i<=26;i++)
        {
            if(i==t.a&&!t.b)continue;
            if(l[i]+t.b<=l[t.a])//若短序列拼接后的新序列比原来长序列短
            {
                int u=a[i][l[i]]*x[t.b]%p1;//原长序列哈希值
                int v=(a[t.a][l[i]+t.b]-a[t.a][t.b]+p1)%p1;//新序列哈希值
                if(u==v)p.push({t.a,t.b+l[i]});
            }
            else
            {
                int u=a[i][l[t.a]-t.b]*x[t.b]%p1;
                int v=(a[t.a][l[t.a]]-a[t.a][t.b]+p1)%p1;
                if(u==v)p.push({i,l[t.a]-t.b});
            }
        }
    }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    x[0]=1;
    for(int i=1;i<=1145141;i++)x[i]=x[i-1]*x1%p1;
    cin>>t;
    while(t)
    {
        t--;
        for(int i=1;i<=26;i++)cin>>s[i],s[i]=' '+s[i];
        for(int i=1;i<=26;i++)
        {
            l[i]=s[i].size()-1;
            k[i]=k[i-1]+l[i];a[i].push_back(0);
            for(int j=1;j<=l[i];j++)
            {
                int u=s[i][j]-'a'+1;
                int o=u*x[j];
                if(j)o+=a[i][j-1];o%=p1;
                a[i].push_back(o);
            }
        }
        for(int i=1;i<=26;i++)p.push({i,0});
        int q=bfs();
        if(q)cout<<"Ruzan"<<endl;
        else cout<<"Krasan"<<endl;
        for(int i=1;i<=26;i++)a[i].clear();
        for(int i=0;i<=k[26];i++)v[i]=0;
        while(p.size())p.pop();
    }
    return 0;
}