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

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

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

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

Q&A

解決済

2回答

3947閲覧

2つの文字列を比較して、共通の文字列を抜き出すプログラムが書きたいです。

uuushiro

総合スコア41

Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

0グッド

0クリップ

投稿2017/04/15 01:31

###前提・実現したいこと
入力の一行目と二行目で与えられる2つの文字列を比較し、共通な文字列を全て抜きだすプログラムが書きたいです。

###具体的な問題

例1 入力値: ABC BCD 出力値: BC 例2 入力値: AKIFHEKDODHJEKOPFJDNEKFIDENJFHGROPEEWMDJFH OJEEKOPFJDDKJGHGIUREMNGHGODPLEJFHEWMDJ 出力値: EKOPFJD EWMDJ

###試したこと
rubyのgemである、differを用いると簡単に実装できるようです。

ruby

1 def compare(word1, word2) 2 words = [] 3 words << word1 4 words << word2 5 strs.reduce do |s1, s2| 6 #Differ.diff_by_char()というメソッドは以下のように2つの文字列を文字単位で比較し、差分を返す。 7 s = Differ.diff_by_char(s1,s2).to_s 8 s[0..s.index('{')-1] 9 end 10 end

ただ、この問題は勉強になりそうで、gemの力を借りずに実装したいと思いました。

どなたか方針でも教えていただけないでしょうか。

###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報

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

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

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

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

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

guest

回答2

0

基本的に、この手の問題は文字列二つを重ねて
一文字づつずらしていく

ruby

1 2ABCDEFGA 3     AEFGDCB 4XXXXXXXOXXXXX 5ABCDEFGA 6     AEFGDCB 7XXXXXXXXXXXX 8ABCDEFGA 9   AEFGDCB 10XXXXXXXXXXX 11ABCDEFG 12   AEFGDCB 13XXXXOOOXXX 14#以下略

Xは上下が等しくないOは上下が等しい
の極値解を取るのが一番早いと言われています。
でdiffer中身を見たところおそらくこれを使っていません
BeatStarさんのいう内容のruby実装のようです。(正確には見きれていませんが)
他に似たようなライブラリが無いなら、ぜひライブラリを作って公開してください。
まあ、この方法で書いたRubyの実装がCとして最速という保証は無いので
String Class に & methodとしてRubyにCで実装してくれたら嬉しいです。

投稿2017/04/15 08:28

編集2017/04/15 08:29
moke

総合スコア2241

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

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

uuushiro

2017/04/15 13:49

一文字づつずらしていくのですね! 具体的には、どのように文字列をずらしていき、比較するのでしょうか? 配列に格納した後の、操作方法が思いつきません。
guest

0

ベストアンサー

私自身はC/C++で趣味でやっています。

外部ライブラリ等を使わずに...となると、

自分で分解する必要があると思います。

C言語では String とかのような 文字列用の変数やクラスが存在しません。

ではどうやっているか...

配列に格納しています。

たとえば

str[0] = 'h'
str[1] = 'e'
str[2] = 'l'
str[3] = 'l'
str[4] = 'o'

のような感じです。

こう考えると、

私なら、

文字列1 = "ABC"
文字列2 = "BCE"

としたら、

まず

文字列1 の 0番目 (つまり 'A' ) が 文字列2 にあるかどうかを for文かなんかでチェックします。

もし、無いなら次のスペルへ移りますが、

もしあるなら、文字列1 にも 文字列2 にもあるということなので

共通用の配列かなんかに この 'A' をセットします。

今回の場合は 'A' は 文字列2 にはないので 無視。

次のスペルは 'B' ですね。

同じように 文字列2 に 'B' があるかどうかチェックします。

あるので 結果用の配列かなんかにセット。

...

と文字列1 の最終文字まで行う。

これでOKだと思います。

文字列2 をチェックしてもいいですが。

投稿2017/04/15 07:50

BeatStar

総合スコア4958

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

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

uuushiro

2017/04/15 13:47

ありがとうございます。 なるほど文字列を配列として扱うのですね!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問