Scalaの勉強はじめました 2 〜文字列検索と深さ優先探索〜

はじめに

N予備校の「Scala基礎」を受講しています。

検索

索引型検索

文章の中からあらかじめ単語の文字列を抜き出して、単語ごとに索引を作っておく検索方法

あらかじめインデックスを作るイメージ

非索引型検索

与えられた文字の情報のみを用いて検索を行う

文章を全て走査するので時間がかかる

val text = "ネコネコネコネコイヌイヌイヌイヌネコネコワンコイヌイヌネコネコワンコ".toSeq
  val pattern = "ワンコ".toSeq
  val matchIndexes = search(text, pattern)

  def search(text: Seq[Char], pattern: Seq[Char]): Seq[Int] = {
    // 型を明示する
    var matchIndexes = Seq[Int]()
    // 文字列を検索
    for (i <- 0 to text.length - 1){
      // i文字目から3文字取り出す
      val partText = text.slice(i, i + pattern.length)
      if (isMatch(partText, pattern)) {
        matchIndexes = matchIndexes :+ i
      }
      println(partText)
    }
    matchIndexes
  }

isMatchは検索に引っ掛かればtrueを返すようにする。

正規表現を使う

val matchIndexes = pattern.r.findAllIn(text).matchData.map(_.start).toList

Stringのrメソッド
文字列を正規表現のRegex型に変換する

findAllIn
Regex型のメソッドで、与えられた正規表現にマッチするIteratorを取得し、MatchIterator型を返す

matchData
MatchIteratorのmatchDataフィールド
マッチした文字列に対するさまざまな情報を含む、Iterator[Match]型を返す

Iterator
イテレータという何らかの要素の集合を巡回しながらアクセスできる型。 巡回可能なコレクションのような振る舞いを提供する。

_.start
Match型を start: Int というマッチした時の出現箇所のインデックスに変換。_を使うことで、map関数を適用しようとしているコレクションの要素のメソッドも呼び出すことができる

深さ優先探索

1 回の呼び出しの中で、数列の 1 番目の要素を「足す場合」と「足さない場合」の 2 つの 再帰呼び出しをすることで、 最終的に全てのパターンを網羅する実装方法

部分和問題

val a = Seq(3, 6, -5, 7)
  val n = a.length
  val k = 9
  
  def isMatchAndResult(index: Int, partial: Seq[Int]): (Boolean, Seq[Int]) = {        
    println(s"index: ${index}, partial: ${partial}")
    if (index == n){
      return if (partial.sum == k)(true, partial) else (false, Seq())      
    }
    
    val (isMatchNotAdd, resultNotAdd) = isMatchAndResult(index + 1, partial)
    if(isMatchNotAdd) return (isMatchNotAdd, resultNotAdd)    
    
    isMatchAndResult(index + 1, partial :+ a(index))    
  }
  val (isMatch, result) = isMatchAndResult(0, Seq())

正直これ見てもちょっとわからなかったです。
絵を見てようやく理解できた感じ。

まとめ

再帰呼び出しはそもそも何を実現しようとしているのかを把握しないと、自力で変数の中を追うにも限界があるなと。