connected_names.rb

class UnionFind

  def initialize
    @parents = Hash.new{|h, s| h[s] = s}
    @ranks = Hash.new{|h, s| h[s] = 0}
  end

  def find(i)
    parent = @parents[i]
    if i == parent
      return i
    else
      @parents[i] = find(parent)
      return @parents[i]
    end
  end

  def unite(i, j)
    i_root = find(i)
    j_root = find(j)
    if i_root != j_root
      if @ranks[i_root] > @ranks[j_root]
        @parents[j_root] = i_root
      elsif @ranks[j_root] > @ranks[i_root]
        @parents[j_root] = i_root
      else
        @parents[j_root] = i_root
        @ranks[i_root] += 1
      end
    end
  end

  def connected?(i, j)
    return find(i) == find(j)
  end

end


NAMES = DATA.read.split(/\s*\n\s*/)
LENGTH = 2

tree = UnionFind.new
NAMES.each do |name|
  name.chars.each_cons(LENGTH) do |array|
    part = array.join
    NAMES.each do |search_name|
      if search_name.include?(part)
        tree.unite(name, search_name)
      end
    end
  end
end

result = NAMES.group_by{|s| tree.find(s)}.map{|_, g| g.join(", ")}.join("\n-----\n")
puts("length = #{LENGTH}")
puts
puts(result)


__END__
しまむらうづき
なかのゆか
みずもとゆかり
ふくやままい
しいなのりこ
いまいかな
もちだありさ
みむらかなこ
おくやまさおり
まなかみさと
こひなたみほ
おがたちえり
いがらしきょうこ
やなせみゆき
さくらいももか
えがみつばき
ながとみはすみ
よこやまちか
せきひろみ
おおたゆう
むなかたあつみ
ふじもとりな
おおはらみちる
ゆさこずえ
おおぬまくるみ
いちのせしき
まえかわみく
あかにしえりか
まつばらさや
あいはらゆきの
みやもとふれでりか
こばやかわさえ
さいおんじことか
ふたばあんず
やおふぇいふぇい
ももいあずき
すずみやせいか
つきみやみやび
ひょうどうれな
にわひとみ
どうみょうじかりん
やなぎきよら
いむらせつな
くさかべわかば
さかきばらさとみ
こしみずさちこ
あんざいみやこ
あさのふうか
おおにしゆりこ
あべなな
くどうしのぶ
くりはらねね
こがこはる
くらりす
さくままゆ
むらまつさくら
しらぎくほたる
はやさかみれい
ありうらかんな
おとくらゆうき
はらだみよ
いけぶくろあきは
しぶやりん
くろかわちあき
まつもとさりな
きりのあや
たかはしれいこ
あいかわちなつ
かわしまみずき
かみやなお
かみじょうはるな
あらきひな
とうごうあい
ただりいな
みずきせいら
ささきちえ
みふねみゆ
はっとりとうこ
きばまなみ
ふじわらはじめ
にったみなみ
みずのみどり
ふるさわよりこ
たちばなありす
さぎさわふみか
やがみまきの
らいら
あさりななみ
へれん
まつながりょう
こむろちなみ
たかみねのあ
たかがきかえで
かんざきらんこ
いじゅういんめぐみ
ひいらぎしの
ほうじょうかれん
けいと
せなしおり
あやせほのか
さじょうゆきみ
しのはられい
わくいるみ
よしおかさき
うめきおとは
しらさかこうめ
きしべあやか
うじいえむつみ
にしかわほなみ
なるみやゆめ
ふじいとも
しおみしゅうこ
わきやまたまみ
おかざきやすは
はやみかなで
おおいしいずみ
まつおちづる
もりくぼのの
あなすたしあ
やまとあき
ゆうきはる
にのみやあすか
きりゅうつかさ
もちづきひじり
たかふじかこ
ほんだみお
たかもりあいこ
なみきめいこ
りゅうざきかおる
きむらなつき
まつやまくみこ
さいとうようこ
さわだまりな
やぐちみう
あかぎみりあ
あいのなぎさ
まなべいつき
おおつきゆい
ひめかわゆき
きたみゆず
うえだすずほ
えびはらなほ
おいかわしずく
こせきれいな
えとうみさき
ほししょうこ
かたぎりさなえ
ほりゆうこ
にしじまかい
まとばりさ
ざいぜんときこ
よりたよしの
あいばゆみ
ののむらそら
はまかわあゆな
わかばやしともか
じょうがさきみか
じょうがさきりか
せんざきえま
ひのあかね
もろぼしきらり
とときあいり
なたーりあ
そうまなつみ
まきはらしほ
むかいたくみ
いちはらにな
きたひなこ
すぎさかうみ
きたがわまひろ
めありーこくらん
こまついぶき
みよしさな
きゃしーぐらはむ
なんばえみ
はまぐちあやめ
むらかみともえ
つちやあこ
しゅとうあおい
さえじまきよみ
さとうしん
なんじょうひかる
いゔさんたくろーす

result_2.txt

length = 2

しまむらうづき, なかのゆか, みずもとゆかり, ふくやままい, しいなのりこ, いまいかな, もちだありさ, みむらかなこ, おくやまさおり, まなかみさと, こひなたみほ, おがたちえり, いがらしきょうこ, やなせみゆき, さくらいももか, えがみつばき, ながとみはすみ, よこやまちか, せきひろみ, おおたゆう, むなかたあつみ, ふじもとりな, おおはらみちる, おおぬまくるみ, いちのせしき, まえかわみく, あかにしえりか, まつばらさや, あいはらゆきの, みやもとふれでりか, こばやかわさえ, さいおんじことか, ふたばあんず, ももいあずき, すずみやせいか, つきみやみやび, ひょうどうれな, にわひとみ, どうみょうじかりん, やなぎきよら, いむらせつな, くさかべわかば, さかきばらさとみ, こしみずさちこ, あんざいみやこ, あさのふうか, おおにしゆりこ, あべなな, くどうしのぶ, くりはらねね, こがこはる, くらりす, さくままゆ, むらまつさくら, しらぎくほたる, はやさかみれい, ありうらかんな, おとくらゆうき, はらだみよ, いけぶくろあきは, しぶやりん, くろかわちあき, まつもとさりな, きりのあや, たかはしれいこ, あいかわちなつ, かわしまみずき, かみやなお, かみじょうはるな, あらきひな, とうごうあい, ただりいな, みずきせいら, ささきちえ, みふねみゆ, はっとりとうこ, きばまなみ, ふじわらはじめ, にったみなみ, みずのみどり, ふるさわよりこ, たちばなありす, さぎさわふみか, やがみまきの, らいら, あさりななみ, へれん, まつながりょう, こむろちなみ, たかみねのあ, たかがきかえで, かんざきらんこ, いじゅういんめぐみ, ひいらぎしの, ほうじょうかれん, けいと, せなしおり, あやせほのか, さじょうゆきみ, しのはられい, わくいるみ, よしおかさき, うめきおとは, しらさかこうめ, きしべあやか, うじいえむつみ, にしかわほなみ, なるみやゆめ, ふじいとも, しおみしゅうこ, わきやまたまみ, おかざきやすは, はやみかなで, おおいしいずみ, まつおちづる, もりくぼのの, やまとあき, ゆうきはる, にのみやあすか, きりゅうつかさ, もちづきひじり, たかふじかこ, ほんだみお, たかもりあいこ, なみきめいこ, りゅうざきかおる, きむらなつき, まつやまくみこ, さいとうようこ, さわだまりな, やぐちみう, あかぎみりあ, あいのなぎさ, まなべいつき, おおつきゆい, ひめかわゆき, きたみゆず, うえだすずほ, えびはらなほ, おいかわしずく, こせきれいな, えとうみさき, ほししょうこ, かたぎりさなえ, ほりゆうこ, にしじまかい, まとばりさ, ざいぜんときこ, よりたよしの, あいばゆみ, ののむらそら, はまかわあゆな, わかばやしともか, じょうがさきみか, じょうがさきりか, せんざきえま, ひのあかね, もろぼしきらり, とときあいり, なたーりあ, そうまなつみ, まきはらしほ, むかいたくみ, いちはらにな, きたひなこ, すぎさかうみ, きたがわまひろ, めありーこくらん, こまついぶき, みよしさな, きゃしーぐらはむ, なんばえみ, はまぐちあやめ, むらかみともえ, つちやあこ, しゅとうあおい, さえじまきよみ, さとうしん, なんじょうひかる, いゔさんたくろーす
-----
ゆさこずえ
-----
やおふぇいふぇい
-----
あなすたしあ

result_3.txt

length = 3

しまむらうづき
-----
なかのゆか
-----
みずもとゆかり
-----
ふくやままい, おくやまさおり
-----
しいなのりこ
-----
いまいかな
-----
もちだありさ
-----
みむらかなこ, むらかみともえ
-----
まなかみさと
-----
こひなたみほ
-----
おがたちえり
-----
いがらしきょうこ, ほししょうこ
-----
やなせみゆき
-----
さくらいももか, むらまつさくら
-----
えがみつばき
-----
ながとみはすみ
-----
よこやまちか
-----
せきひろみ
-----
おおたゆう
-----
むなかたあつみ
-----
ふじもとりな
-----
おおはらみちる
-----
ゆさこずえ
-----
おおぬまくるみ
-----
いちのせしき
-----
まえかわみく
-----
あかにしえりか
-----
まつばらさや, さかきばらさとみ
-----
あいはらゆきの
-----
みやもとふれでりか
-----
こばやかわさえ
-----
さいおんじことか
-----
ふたばあんず
-----
やおふぇいふぇい
-----
ももいあずき
-----
すずみやせいか
-----
つきみやみやび
-----
ひょうどうれな
-----
にわひとみ
-----
どうみょうじかりん
-----
やなぎきよら
-----
いむらせつな
-----
くさかべわかば, わかばやしともか
-----
こしみずさちこ
-----
あんざいみやこ
-----
あさのふうか
-----
おおにしゆりこ
-----
あべなな
-----
くどうしのぶ
-----
くりはらねね
-----
こがこはる
-----
くらりす
-----
さくままゆ
-----
しらぎくほたる
-----
はやさかみれい
-----
ありうらかんな
-----
おとくらゆうき, ゆうきはる
-----
はらだみよ
-----
いけぶくろあきは
-----
しぶやりん
-----
くろかわちあき, あいかわちなつ, かわしまみずき, みずきせいら, おいかわしずく
-----
まつもとさりな, あさりななみ
-----
きりのあや
-----
たかはしれいこ
-----
かみやなお
-----
かみじょうはるな, ほうじょうかれん, さじょうゆきみ, じょうがさきみか, じょうがさきりか, なんじょうひかる
-----
あらきひな
-----
とうごうあい
-----
ただりいな
-----
ささきちえ
-----
みふねみゆ
-----
はっとりとうこ
-----
きばまなみ
-----
ふじわらはじめ
-----
にったみなみ
-----
みずのみどり
-----
ふるさわよりこ
-----
たちばなありす
-----
さぎさわふみか
-----
やがみまきの
-----
らいら
-----
へれん
-----
まつながりょう
-----
こむろちなみ
-----
たかみねのあ
-----
たかがきかえで
-----
かんざきらんこ, せんざきえま
-----
いじゅういんめぐみ
-----
ひいらぎしの
-----
けいと
-----
せなしおり
-----
あやせほのか
-----
しのはられい
-----
わくいるみ
-----
よしおかさき
-----
うめきおとは
-----
しらさかこうめ
-----
きしべあやか
-----
うじいえむつみ
-----
にしかわほなみ
-----
なるみやゆめ
-----
ふじいとも
-----
しおみしゅうこ
-----
わきやまたまみ
-----
おかざきやすは
-----
はやみかなで
-----
おおいしいずみ
-----
まつおちづる
-----
もりくぼのの
-----
あなすたしあ
-----
やまとあき
-----
にのみやあすか
-----
きりゅうつかさ, りゅうざきかおる
-----
もちづきひじり
-----
たかふじかこ
-----
ほんだみお
-----
たかもりあいこ
-----
なみきめいこ
-----
きむらなつき
-----
まつやまくみこ
-----
さいとうようこ
-----
さわだまりな
-----
やぐちみう
-----
あかぎみりあ
-----
あいのなぎさ
-----
まなべいつき
-----
おおつきゆい
-----
ひめかわゆき
-----
きたみゆず
-----
うえだすずほ
-----
えびはらなほ
-----
こせきれいな
-----
えとうみさき
-----
かたぎりさなえ
-----
ほりゆうこ
-----
にしじまかい
-----
まとばりさ
-----
ざいぜんときこ
-----
よりたよしの
-----
あいばゆみ
-----
ののむらそら
-----
はまかわあゆな
-----
ひのあかね
-----
もろぼしきらり
-----
とときあいり
-----
なたーりあ
-----
そうまなつみ
-----
まきはらしほ
-----
むかいたくみ
-----
いちはらにな
-----
きたひなこ
-----
すぎさかうみ
-----
きたがわまひろ
-----
めありーこくらん
-----
こまついぶき
-----
みよしさな
-----
きゃしーぐらはむ
-----
なんばえみ
-----
はまぐちあやめ
-----
つちやあこ
-----
しゅとうあおい
-----
さえじまきよみ
-----
さとうしん
-----
いゔさんたくろーす