TCO2011 OR1

過去問といいつつとってもタイムリーな問題です。

Easy TripleStrings

initとgoalが与えられる。initは文字列Aの初期値である。このとき文字列B,Cなどを用いて以下の操作が行えるとしたとき、Aをgoalの状態にするために必要な最小の操作数を答えよ。
(操作)

Aが空文字でないとき、Aの左側一文字をBの最後に付け足す
Aが空文字でないとき、Aの左側一文字をCの最後に付け足す
Bが空文字でないとき、Bの左側一文字をAの最後に付け足す
Cが空文字でないとき、Cの左側一文字をAの最後に付け足す

方針

操作数は必ず偶数になる。なぜならばBやCに移す操作数とAに移す操作数が等しくなければいけないからである。
そして、ここではAの左側から取らなければいけないため、goalの左側にある部分文字列がinitの右側にある部分文字列と等しい場合、この文字列に関しては操作は行われていない。
よって、操作が行われていない最大の部分文字列長をみつけ、Aの長さから引き2倍したものが答えになる。

コード

class TripleStrings {
public:
   int getMinimumOperations( string init, string goal ) {
     if (init==goal) return 0;
     int len = init.length();
     int res=0;
     for (int i=len-1; i>0; i--) {
       //       cout<<goal.substr(0,i)<<" "<<init.substr(len-i,i)<<endl;
       if (goal.substr(0,i)==init.substr(len-i,i)) {
	 res = i;
	 break;
       }
     }
     return (len-res)*2;
   }
};