ABC285 B問題（Longest Uncommon Prefix）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）285 のB問題をC++とPythonで解いてみました。ABC285は、2023年1月15日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 Longest Uncommon Prefix（Difficulty : 108）

問題はリンク先をご覧ください。

ABC285 B問題 Longest Uncommon Prefix

文字列の中で重複している文字を探す問題です。AtCoder Problems による Difficulty は 108 でした。

解答案

問題文に書いてある数式の把握が難しかったです。このような場合は、入力例と出力例を確認しています。この問題については、入力例の計算を確かめて把握ができました。

問題を解く方針を書きだします。問題文では、文字列の添え字を 1 からカウントしていますが、以下では 0 からカウントします。

• N と文字列 S を読み込む。
• 1 から N – 1 まで以下を繰り返す。ループ変数を i とする。
  • 0 から以下を繰り返す。ループ変数を j とする。
    • 0 から連続して S[j] と S[i + j] が等しくならない最大の j を求める。
    • j を出力する。
      ※0 から j-1 まで一致していない。つまり、j 個が一致していない。

C++ プログラム例（ABC285B）

方針に従いプログラムしました。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;


	for (int i = 1; i < n; ++i) {
		int result = 0;
		for (int j = 0; i + j < s.length(); ++j) {
			if (s[j] != s[i + j]) {
				++result;
			} else {
				break;
			}
		}
		cout << result << endl;
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC285B）

Python 版として、C++ のプログラムをそのまま移植しました。

"""AtCoder Beginner Contest 285 B"""
n = int(input())
s = input()
for i in range(1, n):
    result = 0
    for j in range(len(s) - i):
        if s[j] != s[i + j]:
            result += 1
        else:
            break
    print(result)

このプログラムは、PyPy3（7.3.0）では、AC 判定でしたが、Python（3.8.2）では、TLE（Time Limit Exceeded）となりました。

処理時間を改善するため、以下を変更しました。

• 文字列からリストに変更する。
• 文字列の長さを毎回求めるのではなく、n を参照する。
• result のインクリメントを避けるロジックに変更する。

以下が、改善したプログラムです。

"""AtCoder Beginner Contest 285 B"""
n = int(input())
s = list(input())
for i in range(1, n):
    result = n - i
    for j in range(n - i):
        if s[j] == s[i + j]:
            result = j
            break
    print(result)

このプログラムは、PyPy3（7.3.0）と Python（3.8.2）のどちらも AC（Accepted＝正しいプログラム）と判定されました。

Python について、まだまだ習熟度が足りないことが分かりました。

最後に

問題文を読んで把握ができず、入力例から理解した問題でした。また、効率（主に時間面）で、Python について、まだまだ理解不足だと感じました。

引き続き ABC の問題を紹介していきます。