下面是代码，中间的变量输出是为了调试。

#include<bits/stdc++.h>
using namespace std;
const int maxn=25;
string a,b,sj[10][2];
int cnt,nxt[maxn];
void get(string s){
    nxt[0]=nxt[1]=0;
    for(int i=1;i<s.size();++i){
        int j=nxt[i];
        while(j && s[i]!=s[j]){
            j=nxt[j];
        }
        if(s[i]==s[j]){
            nxt[i+1]=nxt[j+1];
        }
        else{
            nxt[i+1]=0;
        }
    }
}
int kmp(string s,string p,int pre){
    if(p.size()>s.size()){
        return -1;
    }
    int j=0;
    for(int i=pre+1;i<s.size();++i){
        while(j && s[i]!=p[j]){
            j=nxt[j];
        }
        if(s[i]==p[j]){
            ++j;
            if(j==p.size()){
                return i-j+1;
            }
        }
    }
    return -1;
}
void bfs(queue<string> &qa,queue<string> &qb,
    map<string,int> &mpa,map<string,int> &mpb,bool isa){
    string now=qa.front();
    qa.pop();
    cout<<(isa?"astr:":"bstr:")<<' '<<now<<' '<<mpa[now]<<endl;
    cout<<"cnt:"<<cnt<<endl;
    get(now);
    for(int i=0;i<cnt;++i){
        int k;
        if(isa){
            k=kmp(now,sj[i][0],-1);
            cout<<i<<' '<<sj[i][0]<<" k:"<<k<<endl;
        }
        else{
            k=kmp(now,sj[i][1],-1);
            cout<<i<<' '<<sj[i][1]<<" k:"<<k<<endl;
        }
        int pre=0;
        while(k!=-1){
            //cout<<k<<endl;
            pre=k;
            string s;
            if(isa){
                s=now.substr(0,k)+sj[i][1]+
                now.substr(k+sj[i][0].size());
            }
            else{
                s=now.substr(0,k)+sj[i][0]+
                now.substr(k+sj[i][1].size());
            }
            if(mpa.count(s)){
                break;
            }
            if(mpb.count(s)){
                if(mpa[now]+mpb[s]+1<11){
                    cout<<mpa[now]+mpb[s]+1;
                }
                else{
                    cout<<"NO ANSWER!";
                }
                exit(0);
            }
            mpa[s]=mpa[now]+1;
            qa.push(s);
            cout<<"push:"<<s<<endl;
            if(isa){
                k=kmp(now,sj[i][0],pre);
            }
            else{
                k=kmp(now,sj[i][1],pre);
            }
        }
    }
}
int main(){
    cin>>a>>b;
    for(;cin>>sj[cnt][0]>>sj[cnt][1];++cnt){
        
    }
    queue<string> qa,qb;
    map<string,int> mpa,mpb;
    qa.push(a);
    mpa[a]=0;
    qb.push(b);
    mpb[b]=0;
    while(!qa.empty() && !qb.empty()){
        if(qa.size()<qb.size()){
            bfs(qa,qb,mpa,mpb,1);
        }
        else{
            bfs(qb,qa,mpb,mpa,0);
        }
    }
    cout<<"NO ANSWER!";
    return 0;
}

我测了一下这个：

input:

a aaaaa
a a112233445566778899
778899 a
112233 a
445 a
566 a
55 a

ans:

5

发现cnt神秘地从6变成了1。这是什么情况？