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

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

ただいまの
回答率

90.85%

  • Python 3.x

    4428questions

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

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

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 979

nagito

score 10

前提・実現したいこと

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の出力の字数が足りなくなってしまうのでしょうか。
どこを改善すれば、最大の共通文字列を出力できますか?
よろしくお願いします。

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+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 が変化しているかが
わかると思います。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/01/13 02:28

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

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

    キャンセル

  • 2017/01/15 16:56

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

    キャンセル

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

  • ただいまの回答率 90.85%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 受付中

    連続した数字の和を求めたい

    Python2.7を使っています。 text.txtというファイルがあり、中には数字が羅列しています。 1234680...といった具合です。 これらの和を求めようとしていま

  • 受付中

    Python:メソッドの引数について

    Python初心者です。 下記のようなメソッドがあったときにint型の引数をうまく共有するような方法はないでしょうか。 count用のクラスを作成する方法もあるかと思います

  • 解決済

    【超初心者質問】pythonの関数の呼び出しに関して

    前提・実現したいこと 今日からプログラミングの勉強を始めたものです。 現在簡単なゲームを作ろうとしているのですが、関数の呼び出しができません。 経験者の方からしたら何でもない

  • 受付中

    ターミナルで実行するのに時間がかかりすぎる

    ターミナルで実行するのに時間がかかりすぎます。 画像圧縮のアルゴリズムを書いています。 N × N ピクセルのグレースケール画像があり各ピクセルの画素値は 0 から 255

  • 解決済

    pythonのスライスについて

    a = b[:,0] このようなコードがあったとき、どのようなことがおこなわれますか? bはこのコードがなりたつ何かだとすると なにだったら成り立ちますか? すみません、間

  • 解決済

    pythonでログの分析(時間)が出来ません。

    前提・実現したいこと pythonのプログラムで質問です。 以下のログがあります。 2012/01/02 13:00 0 2012/01/02 14:00 1 2012/01/

  • 解決済

    Pythonのリストの中の数値の判定

    pythonのリストで質問があります。 log.csv 2017/08/26 08:00, 1, 2017/08/26 08:05, 0, 2017/08/26 09:00, 

  • 解決済

    Python 内包表記

    jupyter notebookでとある数列を求めるプログラムを作りました。 for文の中にあるfor文(for j in range(compare.size + 1)...)を

同じタグがついた質問を見る

  • Python 3.x

    4428questions

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