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; }