二つの文字列から共通部分を抜き出す(Python3)

Question

###前提・実現したいこと
Python3において
「標準入力で取得した二つの文字列s1,s2のうち、連続して共通する最大の文字列を抜き出す」
というプログラムを作成したいです。

###該当のソースコード

s1 = input() #一つ目の文字列取得
L1 = list(s1) #listで一文字ずつに分割
s2 = input() #二つ目の文字列取得
L2 = list(s2) #listで一文字ずつに分割
count = [] #共通部分の抜き出し用
combo, record = 1, 1
coword = [] #最大の文字列出力用

for s in s2: #二つ目の入力の文字を左から一文字ずつ
    if s in s1: #一つ目の入力の文字に二つ目の入力の文字があれば
        count.append(s) #countのリストに格納
        if s1[s1.index(s) - 1] in count: #countのリストに格納されたsがs1の中で連続であれば
            combo += 1 #連続コンボをインクリメント
            if combo > record: #いままでで最もコンボが繋がったら
                record = combo #コンボ記録更新
                coword = count[:record] #countのリストの後ろからrecord字だけ格納
                
        else: #コンボにならなかったら
            combo = 1 #コンボリセット
            
            
print("".join(count)) #比較用
print("".join(coword)) #ここで共通の最大数文字列を出力したい

###実際の入力・出力
出力の1行目はcountのもの、2行目がcowordのものになっています。

入力①

penpineapple
nea

出力①

nea
ne

入力②
penpineapple
iapple

出力②
iapple
iap

###質問
なぜcowordの出力の字数が足りなくなってしまうのでしょうか。
どこを改善すれば、最大の共通文字列を出力できますか？
よろしくお願いします。

Answer 1

解こうとしている問題を私が勘違いしているのかもしれませんが、次の部分が原因と思います。

 if s1[s1.index(s) - 1] in count

なぜなら s が s1 中に複数あった場合、 s1[s1.index(s) - 1] はいつも同じ場所を指してしまうからです。

プログラムを改造するのではなく、違う発想で作りなおしてみました。
s2 から切り取れる部分文字列のパターンをすべて取り出し、それが s1 中に現れるかを調べています。
一番長い文字列を見つけたいので、部分文字列は長さが長いものから試していき、だんだんに長さを短くするようにしています。

y.rb

def find_longest_substr(s1, s2):
    for length in range(len(s2), 0, -1):
        for p0 in range(len(s2) - length + 1):
            substr = s2[p0:(p0 + length)]
            if substr in s1:
                return(substr)
    return ""

s1 = input() #一つ目の文字列取得
s2 = input() #二つ目の文字列取得
print(find_longest_substr(s1, s2))

実行例

$ python3 y.py
penpineapple 
nea
nea

$ python3 y.py
penpineapple 
iapple
apple

substr を代入したあとに print(substr) を追加して はしらせてみると、どんな風に substr が変化しているかが
わかると思います。

Comments

[退会済みユーザー]

ありがとうございます！indexメソッドのあとにスライスでの要素の削除を忘れていました！

このコードのほうが短くてきれいですね！

[katoy]

部分文字列の候補は、短い文字列側を使って生成するようにしたほうが、すこし計算量が減るとおもいます。