重複する箇所を重ねて文字列を結合する(python3)

記事を書いた動機

自身のpythonのプログラム練習としてpaizaの問題を解いていた。
その中でも、paizaのサービスの一つである「エンジニアが死滅シタ世界　アンドロイドとふたりぼっちで生きろ」で詰まった問題があり、解決に手間取った。なかなか気づきにくく同じ問題に直面している人がいるかもしれないため、その時の実装の流れと詰まった原因を書き残す。

問題の内容

n個の文字列が提示され、それらを順に結合した文字列を出力する問題。
ただし新たに結合する文字列の最初と前の文字列の最後で重複する箇所があれば、重なった部分を省略して結合を行う。

以下の入力例では、「kyuri」最後の文字「ri」が「ringo」の最初の二文字と同じため、「ri」を除いた「ngo」を結合する。

入力例

3
kyuri
ringo
sakura

#出力結果
kyuringosakura

処理方法

まず、実装にあたり以下の手順で行った。

1. 空の出力結果文字列resultを宣言(単語を順次結合していく)

2. 入力文字列をwordに代入

3. resultの最後の文字とwordの最初の文字を比較し、合致している場合はresultから最後の文字を削除

4. resultにwordを結合する(文字をくっつける)

5. 入力文字列の数だけ2～4を繰り返す

初期コード

上記の処理方法を踏まえて以下のコードを実行した。

python.py

n = int(input()) #文字列の数
result = "" # 出力結果を格納する変数

#結合を行う処理
for _ in range(n):
    word = input().rstrip()
    word_length = len(word)
    
    # 最初の入力単語なら合致の検証を無視する
    if result != "": 
    
        # max_len : 最大で合致する可能性のある文字列の長さ
        max_len = word_length if word_length < len(result) else len(result) 
        
        # 合致の検証を行う
        for i in range(max_len , 0, -1):
            if word[:i] == result[-i:]:
                result = result[0:len(result)-i]
    
    result = result + word
    
print(result)

用意されていた入力例で問題なく動作したのを確認し提出したところ、不正解だった。このことから、特定の入力で正常な処理が行われていないことが分かった。

反例となる入力をいくつか考えたが見つけられなかったため、ChatGPTに聞きさまざまな入力を試した。

その結果、以下の入力では処理が正常に行われていないことが分かった。

反例

3
banana
ananana
nana

#正解の出力結果
bananana
#プログラム実行結果
banana # 結合がうまくいっていない

原因

反例で行われている処理をひとつずつ考えると、for文内の文字列の合致を確かめる箇所に問題があることが分かった。

nanaの結合を行う際に、最後の文字を削除する処理が行われているが本来一回だけ行う処理が複数回実行されており、削除しなくてもいい箇所も削除され結合がおかしくなっていた。

以下に反例での実行の流れを示す。(問題の箇所のみ記載)

1. bananana(anananaを結合した結果)にnanaを結合していく

2. nanaが一致したため,banananaから最後のnanaを削除しbanaとなる。

3. naの合致の検証が行われ、naが一致したため、banaから最後のnaを削除しbaとなる。（この処理が問題の原因)

4. baにnanaを結合しbananaとなる

そのため、resultの最後の文字を削除する箇所の後にbreakを追加し複数回resultの最後の文字列が削除されないようにした。

python.py

n = int(input())

result = ""
for _ in range(n):
    word = input().rstrip()
    word_length = len(word)
    if result != "":
        max_len = word_length if word_length < len(result) else len(result) 
        for i in range(max_len , 0, -1):
            if word[:i] == result[-i:]:
                result = result[0:len(result)-i]
                break #合致の検証を終了する
        
    result = result + word
    
print(result)

修正したプログラムでは反例も正しく処理されるようになり、再度提出すると正解することができた。