AtCoder が提供しているABC（AtCoder Beginner Contest）280 のC問題をC++とPythonで解いてみました。ABC280は、2022年12月3日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Extra Character（Difficulty : 64）
問題はリンク先をご覧ください。
2つの文字列を比較して、最初に差があるインデックスを出力する問題です。AtCoder Problems による Difficulty は、64 でした。
解答案
問題を解く方針を書きだします。
- 文字列 S と 文字列 T を読み込む。
- S と T を比較して、一致しない最初のインデックスを出力する。
C++ プログラム例（ABC280C）
方針に従いプログラムしますが、注意点があります。文字列 T の末尾に文字を加える場合があります。この場合、文字列 S の長さの範囲では、文字列は一致します。
文字列 S の長さの範囲で、文字列 T と一致した場合は、文字列 T の長さ（＝文字列 S の長さ + 1）を出力します。
解答は、場所の先頭を 1 からカウントしています。配列の先頭は、添え字 0となるため、1 を加えて出力しています。
以下が、C++の実装例です。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
for (int i = 0; i < s.length(); ++i) {
if (s[i] != t[i]) {
cout << i + 1 << endl;
return 0;
}
}
cout << t.length() << endl;
return 0;
}C++ の string は、s[s.length()] に ’\0′ が格納されていることが保証されています。これは、Ｃの文字列と整合を取るためです。このため、string は、実際の文字数よりも1個多い文字列のバッファを持っています。
挿入される英小文字は、’\0′ ではありません。このため、以下のように文字列 S の長さ + 1（=文字列 T の長さ）まで比較することができます。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
for (int i = 0; i <= s.length(); ++i) {
if (s[i] != t[i]) {
cout << i + 1 << endl;
break;
}
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC280C）
Python の場合は、文字列 S の長さの範囲で比較しました。その範囲で一致していれば、文字列 T の長さを出力しました。
for 文を break で抜けていないときにだけ通過する else を使いました。
"""AtCoder Beginner Contest 280 C"""
s = input()
t = input()
for i in range(len(s)):
if s[i] != t[i]:
print(i + 1)
break
else:
print(len(t))こちらも「AC」と判定されました。
最後に
文字列の違いを判定するアルゴリズムは、興味深いものがあります。今回は、一番簡単な難易度の問題だと思われますが、もっと複雑な場合も解けるようになりたいと考えています。
引き続き ABC の問題を紹介していきます。
