AOJ 1296 Repeated Substitution with Sed

string:size_typeとかstring:nposとかよく知らなかったので調べながら書いた。BFSで調べていくが、文字列の長さで枝刈りするだけではTLEしたので、setで既に生成された文字列をメモした。

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)

string rp(string str,string a,string b){
    string res=str;
    string::size_type pos=res.find(a);
    while(pos!=string::npos){
        res.replace(pos,a.size(),b);
        pos=res.find(a,pos+b.size());
    }
    return res;
}

int main(){
	int n;
    while(cin >> n && n){
        vector<string> a(n),b(n);
        string s,g;
        REP(i,n) cin >> a[i] >> b[i];
        cin >> s >> g;
        queue<pair<string,int> > que;
        set<string> st;
        que.push(make_pair(s,0));
        st.insert(s);
        int res=-1;
        while(!que.empty()){
            pair<string,int> p=que.front();
            que.pop();
            if(p.first==g){
                res=p.second;
                break;
            }
            REP(i,n){
                string tmp=rp(p.first,a[i],b[i]);
                if(tmp.length()>g.length()) continue;
                if(st.find(tmp)!=st.end()) continue;
                que.push(make_pair(tmp,p.second+1));
                st.insert(tmp);
            }
        }
        cout << res << endl;
    }
	return 0;
}