VK Cup 2015 Round 2 : E. Correcting Mistakes

一見簡単な問題ながら、完全に見落としてWAしてしまった。
http://codeforces.com/contest/533/problem/E

問題

N文字の異なる文字列S,Tが与えられる。
ある(N+1)文字の文字列Wで、そこから1文字を取り除いてS,Tが作れるようなものは何個あるか。

解法

S[i]!=T[i]となる最初のiを求める。
するとWの候補は以下の2通りである。

• S[0..(i-1)] + S[i] + T[i..(N-1)]
• S[0..(i-1)] + T[i] + S[i..(N-1)]

これら2通りについて、1文字削除してS・Tが作れるか、すなわち部分文字列としてS,Tを含むか判定すればよい。

int L;
string S,T,C[2];

int incl(string lar,string sm) {
	int x=0;
	FORR(r,lar) if(x<sm.size() && sm[x]==r) x++;
	return x==sm.size();
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>S>>T;
	FOR(i,L) if(S[i]!=T[i]) {
		C[0]=S.substr(0,i)+S.substr(i,1)+T.substr(i);
		C[1]=S.substr(0,i)+T.substr(i,1)+S.substr(i);
		break;
	}
	cout<< (incl(C[0],S)&&incl(C[0],T)) + (incl(C[1],S)&&incl(C[1],T)) << endl;
}

まとめ

本番、S,Tで2か所以上の文字が異なるケースでもWが2個になる場合を考慮しきれなかった。