公式

D - Unvarnished Report 解説 by en_translator


There are several implementation approaches; for example, it can be solved with the following algorithm.
Hereinafter, let \(|S|\) and \(|T|\) denote the length of \(S\) and \(T\), respectively, and \(S_i\) and \(T_i\) denote the \(i\)-th characters of \(S\) and \(T\), respectively.

  1. Let \(N\) be the smaller of the lengths of \(S\) and \(T\); i.e., \(N=\min(|S|,|T|)\).
  2. For each \(i=1,2,\ldots,N\), check if \(S_i\) equals \(T_i\). If they are not, print \(i\) and terminate the procedure.
  3. Otherwise, i.e. if \(S_i=T_i\) for all \(i=1,2,\ldots,N\), print \(0\) if \(|S|=|T|(=N)\) and \(N+1\) otherwise.

This algorithm prints \(0\) if \(S\) and \(T\) are equal, and the first different character otherwise. In step \(3.\), note that exactly one of \(S\) and \(T\) has the \((N+1)\)-th character, by definition of \(N\).

This can be implemented using for and if statements.
Thus, the problem has been solved.

Sample code in 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;
}

Sample code in 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

投稿日時:
最終更新: