Official

B - Unvarnished Report Editorial by mechanicalpenciI


実装する方法はいくつか考えられますが、例えば次のようなアルゴリズムで答えを求めることができます。
以下では、\(|S|,|T|\) でそれぞれ \(S,T\) の長さを、\(S_i,T_i\) でそれぞれ \(S,T\)\(i\) 文字目を表すものとします。

  1. \(S\) の長さと \(T\) の長さのうち小さい方を \(N\) とおく。すなわち、\(N=\min(|S|,|T|)\) とする。
  2. \(i=1,2,\ldots,N\) について、順に \(S_i\)\(T_i\) が等しいか判定する。等しくないならば \(i\) を出力して終了する。
  3. 2. で終了しなかったとき、すなわち \(i=1,2,\ldots,N\) すべてについて\(S_i=T_i\) であったとき、\(|S|=|T|(=N)\) ならば \(0\) を、そうでないならば \(N+1\) を出力して終了する。

このとき、\(S\)\(T\) が等しいならば \(0\) を、そうでないとき異なっている文字のうち先頭のものを出力できます。\(3.\) において \(|S|\neq |T|\) のとき、\(N\) の定義より、\(S\), \(T\) のちょうど一方にのみ \(N+1\) 文字目が存在することに注意してください。

これは for文, if 文を用いて実装することができます。
よって、この問題を解くことができました。

c++ による実装例:

#include <bits/stdc++.h>

using namespace std;

int main(void){
	string s,t;
	cin>>s;
	cin>>t;
	int n = min(s.size(),t.size());
	for(int i=0;i<n;i++){
		if(s[i]!=t[i]){
			cout<<(i+1)<<endl;
			return 0;
		}
	}
	if(s.size()!=t.size())cout<<(n+1)<<endl;
	else cout<<0<<endl;
	return 0;
}

Python による実装例:

s=input()
t=input()
n=min(len(s),len(t))
if s==t:
    print(0)
elif s[:n]==t[:n]:
    print(n+1)
else:
    for i in range(n):
        if s[i]!=t[i]:
            print(i+1)
            break

posted:
last update: