質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

1回答

12193閲覧

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

退会済みユーザー

退会済みユーザー

総合スコア0

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

1グッド

0クリップ

投稿2017/01/12 13:14

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

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

Python

1s1 = input() #一つ目の文字列取得 2L1 = list(s1) #listで一文字ずつに分割 3s2 = input() #二つ目の文字列取得 4L2 = list(s2) #listで一文字ずつに分割 5count = [] #共通部分の抜き出し用 6combo, record = 1, 1 7coword = [] #最大の文字列出力用 8 9for s in s2: #二つ目の入力の文字を左から一文字ずつ 10 if s in s1: #一つ目の入力の文字に二つ目の入力の文字があれば 11 count.append(s) #countのリストに格納 12 if s1[s1.index(s) - 1] in count: #countのリストに格納されたsがs1の中で連続であれば 13 combo += 1 #連続コンボをインクリメント 14 if combo > record: #いままでで最もコンボが繋がったら 15 record = combo #コンボ記録更新 16 coword = count[:record] #countのリストの後ろからrecord字だけ格納 17 18 else: #コンボにならなかったら 19 combo = 1 #コンボリセット 20 21 22print("".join(count)) #比較用 23print("".join(coword)) #ここで共通の最大数文字列を出力したい

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

入力①

penpineapple
nea

出力①

nea
ne

入力②
penpineapple
iapple

出力②
iapple
iap

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

ness👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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

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

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

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

y.rb

python

1def find_longest_substr(s1, s2): 2 for length in range(len(s2), 0, -1): 3 for p0 in range(len(s2) - length + 1): 4 substr = s2[p0:(p0 + length)] 5 if substr in s1: 6 return(substr) 7 return "" 8 9s1 = input() #一つ目の文字列取得 10s2 = input() #二つ目の文字列取得 11print(find_longest_substr(s1, s2))

実行例

$ python3 y.py penpineapple nea nea $ python3 y.py penpineapple iapple apple

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

投稿2017/01/12 16:07

編集2017/01/12 17:47
katoy

総合スコア22324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2017/01/12 17:28

ありがとうございます!indexメソッドのあとにスライスでの要素の削除を忘れていました! このコードのほうが短くてきれいですね!
katoy

2017/01/15 07:56

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問