04.Scalaで文字列探索　 Scala基礎コース

# 目次

* 【講義】文字と文字列
* 【講義】文字列検索について
* 【講義】シンプルな文字列検索のアルゴリズム
* 【講義】for と while
* 【実習】シンプルな文字列検索のアプリケーションの作成
* 【実習】「文書」の切り出し
* 【実習】「パターン」と一致した添字を取得
* 【実習】正規表現を使った文字列検索

# 【講義】文字と文字列

今回は数学ではないが、コンピュータを使う上で便利な機能である、文字列検索を Scala で実装してみよう。

Scala において文字や文字列は1種のデータなので、数値と同じように扱うことが可能。
Scala では String という型を用いて文字列を表現している。

ユーザーフォルダにある `workspace` フォルダの `scala-study` フォルダにて、 `sbt console` を実行して、 REPL を起動して調べてみましょう。

Scala では文字列は、 `"abced"` のように、ダブルクォーテーションで囲って表現する。

```scala:sbt_console
scala> "abcde"
res0: String = abcde
```

そして、 Scala の文字列は、コレクションである Seq 型と同じように添字をつけることで文字を取り出すことができる。

```scala:sbt_console
scala> "abcde"(0)
res1: Char = a
```

このように `()` カッコで、添字の 0 を与えてやると最初の文字である `a` を取り出すことができる。
`Char` は文字の型で文字を意味する英単語 Character の略。

Char は、 2 バイト (16 ビット) のデータで、 Unicode というエンコードで表現された文字となる。
エンコードとは、2進数の数値を文字に対応させる方法。
なお、文字列はダブルクォーテーションで囲むことにより表現してきたが、文字は1文字をシングルクォーテーションで囲むことも可能。

```scala:sbt_console
scala> 'a'
res2: Char = a
```

ダブルクォーテーションで入力した場合は、文字ではなく文字列になってしまうので注意。

```scala:sbt_console
scala> "a"
res3: String = a
```

このように 文字列である String 型になってしまう。

# 【講義】文字列検索について

文字はデータであることがわかったところで、文字列検索について説明する。

実は、文字列検索と言っても二通りのやり方が存在する。
1つが、 **索引型検索** で、もう1つが **非索引型検索** 。

## 索引型検索

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

索引がついた本を思い出してみると分かりやすいだろう。
例えば、ある本の索引で「プログラミング」を調べると 10p, 122p, 212p と書いてあったとする。
すると、 10 ページを開くとプログラミングについて書いてあるというような利用方法。
その本では、あらかじめ単語の内容が本のどこに存在するかを索引に記録して、本につけてあるわけだ。

実際に索引をコンピューターでやる場合は、単語毎に、対象の文章の中でどれくらいその単語が利用されているかや、出現位置などに応じてスコアが計算される。
そしてそのスコアに応じて膨大な文書群の中から適切な文章を探し出せるようになっている。

Google などの Web 検索ではこの索引型検索を利用している。
なおこの索引のことを英語で index という。
配列などの添字のことも index というので、文脈によってどちらのことを指し示すのかには注意が必要。

## 非索引型検索

もう1つの非索引型検索は、索引によって検索するのではなく、与えられた文字の情報のみを用いて検索を行う。

索引型検索とは違い、検索を実行する度に対象の文章のデータをすべて走査する。
そのため、膨大な文章群から検索する場合には、時間がかかってしまう。

ただし、対象のデータが少ない場合には索引を作成しなくて良いため、高速に検索できる。
また、文書が変更される度に索引を更新しなくて良いメリットもある。

なお、この非索引型検索は、エディタ内の文字検索やソフトウェアや Web ページ内の検索によく用いられている。
今回は、この非索引型検索を Scala で実装してみよう。

# 【講義】シンプルな文字列検索のアルゴリズム

今回、検索を実装するに当たって、サンプルは以下のものを利用する。

「文書」としては、

```
カワカドカドカドドワンゴカドカドンゴドワドワンゴドワカワカドンゴドワ
```

とし、検索する「パターン」は、

```
ドワンゴ
```

とする。

この文書の 9 文字目と 21 文字目から `ドワンゴ` という文字列が見つかる。
これを Scala のプログラムに「文書」と「パターン」を与えて出現位置を取得できるようにしてみよう。

実は Scala には便利な機能があり、より少ない記述でこれらを実装することも可能。
ただし今回は、 Scala の学習のために、1文字1文字比較を行いながら文書の「パターン」にマッチする部分があるかを調べる実装を行っていく。

一番簡単な方法は、「文章」の1文字目から検索の「パターン」の長さの文字を切り出して、文字とパターンを1文字ずつ比較していく。
もし、全文字同じならマッチしたこととし、1文字でも違えばマッチしないこととするというもの。

1文字目からの操作が終わったら、今度は「文章」の2文字目から検索の「パターン」の長さの文字を切り出して、同様のことを行う。

そして「文書」の3文字目、4文字目と繰り返し、文章の最後までマッチするものがないか最後まで探す。
マッチした場合はその出現位置を保存しておく。

実際にサンプルの文字列で考えてみよう。

まず最初は、「文書」からドワンゴの4文字分を最初の1文字目から切り出す。

```
カ,ワ,カ,ド,カ,ド,カ,ド,ド,ワ,ン,ゴ,カ,ド,カ,ド,ン,ゴ,ド,ワ,ド,ワ,ン,ゴ,ド,ワ,カ,ワ,カ,ド,ン,ゴ,ド,ワ

↓

カ,ワ,カ,ド
```

切り出したら、 `ドワンゴ` と一文字ずつ比較していく。

```
1 文字目: カ と ド => ☓

2 文字目: ワ と ワ => ○

3 文字目: カ と ン => ☓

4 文字目: ド と ゴ => ☓
```

このようになる。
1つしか合っていない。
結果マッチしない。
次に行く。
今度は2文字目から切り出す。

```
カ,ワ,カ,ド,カ,ド,カ,ド,ド,ワ,ン,ゴ,カ,ド,カ,ド,ン,ゴ,ド,ワ,ド,ワ,ン,ゴ,ド,ワ,カ,ワ,カ,ド,ン,ゴ,ド,ワ

   ↓

   ワ,カ,ド,カ
```

また1文字ずつ比較する。

```
1 文字目: ワ と ド => ☓

2 文字目: カ と ワ => ☓

3 文字目: ド と ン => ☓

4 文字目: カ と ゴ => ☓
```

どの文字も一致せずマッチしない。
あとはひたすらこれを繰り返すだけ。

# 【講義】for と while

実はこの実装をするためには、ループを2回行う必要がある。
Scala にはループを記述するための文法である for 式と while 式がある。
for も if と小津ように「文」ではなく「式」であり、値を返すことが可能。
ただし、この for で値を返す方法に関してはまた別の回で詳しく説明する。

まずは for 式。
REPL を起動して以下のように入力してみよう。

```scala
for (i <- 0 to 10) { println(i) }
```

以上を入力すると、

```scala:sbt_console
scala> for (i <- 0 to 10) { println(i)}
0
1
2
3
4
5
6
7
8
9
10
```

このように表示されるはず。
JavaScript の for 文では、初期化式や条件式、変化式などを記述する必要がある。
一方で Scala では、 0 から 10 のループに関しては `to` という記述を使って、

```scala
for (i <- 0 to 10) { println(i) }
```

のように書くことが可能。
`i` はループ毎の変数の値が入っている。

次の while 式は、 JavaScript の while 文とほぼ同様のもの。
REPL に以下のように入力してみよう。

```scala
var i = 0
while (i <= 10) { println(i); i = i + 1}
```

以上を入力すると、

```scala:sbt_console
scala> var i = 0
i: Int = 0

scala> while (i <= 10) { println(i); i = i + 1}
0
1
2
3
4
5
6
7
8
9
10
```

このように表示される。

while 式は、 while の後の `()` の中の値が true であればずっとループを続ける。

ここでは、変数 i を var で宣言して、それをループ毎に `1` ずつ増やしていく。
そして、条件式が `i <= 10` である、つまり `i` が 10 以下の間でループをするように記述されている。
Scala で命令文は `;` を入れることで、1行で何回も命令文を記述できる。

なお、 while 式には do-while 形式で記述する方法もあり、

```scala
var i = 0
do { println(i); i = i + 1} while (i <= 10)
```

以上を実行すると、

```scala
scala> var i = 0
i: Int = 0

scala> do { println(i); i = i + 1} while (i <= 10)
0
1
2
3
4
5
6
7
8
9
10
```

実行後に `while` の判定を行う形式で実装することも可能。

このように、今回はこのループの機能を使って文字列検索を実装してみよう。

# 【実習】シンプルな文字列検索のアプリケーションの作成

では、 `scala-study` フォルダの中に、 `SimpleSearch.scala` というファイルを作成して以下を実装していこう。

```scala:SimpleSearch.scala
object SimpleSearch extends App {
  val text = "カワカドカドカドドワンゴカドカドンゴドワドワンゴドワカワカドンゴドワ".toSeq
  val pattern = "ドワンゴ".toSeq
  val matchIndexes = Seq()

  println(s"出現場所: ${matchIndexes}")
}
```

以上のように実装する。

検索対象の「文書」が `text` で、検索する「パターン」を `pattern` とする。
これらの定数にそれぞれ `toSeq` を呼び出すことで、 Seq[Char] 型に変換しておく。

答えは、 `matchIndexes` とし、まずここでは仮の答えの空のシーケンスを代入してある。
sbt を起動し、

```scala:sbt
> runMain SimpleSearch
```

以上を実行すると、

```scala:sbt
[info] running SimpleSearch 
出現場所: List()
[success] Total time: 4 s, completed 2021/07/27 11:07:14
```

のように表示されることがわかるだろう。

# 【実習】「文書」の切り出し

次に検索を行う関数を定義して、その中で文章をパターンの文字数分切り出す、ということを先頭から最後までやってみよう。

```scala:SimpleSearch.scala
object SimpleSearch extends App {
  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) {
      val partText = text.slice(i, i + pattern.length)
      println(partText)
    }
    matchIndexes
  }

  println(s"出現場所: ${matchIndexes}")
}
```

以上のように実装してみよう。

無事実装できたら、 `runMain SimpleSearch` で出力を確認する。

```scala:sbt
[info] running SimpleSearch 
カワカド
ワカドカ
カドカド
ドカドカ
カドカド
ドカドド
カドドワ
ドドワン
ドワンゴ
ワンゴカ
ンゴカド
ゴカドカ
カドカド
ドカドン
カドンゴ
ドンゴド
ンゴドワ
ゴドワド
ドワドワ
ワドワン
ドワンゴ
ワンゴド
ンゴドワ
ゴドワカ
ドワカワ
ワカワカ
カワカド
ワカドン
カドンゴ
ドンゴド
ンゴドワ
ゴドワ
ドワ
ワ
出現場所: List()
[success] Total time: 1 s, completed 2021/07/27 11:11:09
```

以上のように表示されれば問題ない。
ここで実装した部分を解説する。

```scala
val matchIndexes = search(text, pattern)
```

これは、 `matchIndexes` を空のシーケンスから、 `search` 関数を呼び出した結果に置き換えている。
`search` 関数には、「文書」と「パターン」を与える。

```scala
def search(text: Seq[Char], pattern: Seq[Char]): Seq[Int] = {
```

以上が、 `search` 関数のインターフェース。
`text` も `pattern` も、 Seq[Char] 型だ。
そして戻り値には出現箇所の添字を取得するために、 Seq[Int] 型にしてある。

```scala
var matchIndexes = Seq[Int]()
```

以上が、関数の中で取得する予定の `matchIndexes` の変数。
変数宣言でも、 `:Seq[Int]` のように書くことで、明示的に型を宣言できる。
初期値は空のシーケンス。

```scala
for (i <- 0 until text.length - 1) {
  val partText = text.slice(i, i + pattern.length)
  println(partText)
}
```

この部分は、 for 式で 0 から「文書」の長さ - 1 までの i でループ処理を行っている。
to で範囲を指定した場合は自身の数を含むが、このように until で指定した場合には、最後の自身の数は含まないように範囲を指定することができる。
なお、 i を「文書」の文字のシーケンスを切り出すために、ここでは、 Seq の [slice](https://www.scala-lang.org/files/archive/api/2.12.6/scala/collection/Seq.html) という関数を用いた。

この `slice` 関数は、第一引数から第二引数までの添字の部分のシーケンスを切り出すことだできる。
そしてその後、 `println` 関数でコンソールに出力させる。

# 【実習】「パターン」と一致した添字を取得

では今度は、パターンが一致したかどうか判定する処理を記述して、一致した場合にはそれを `matchIndexes` のシーケンスに保存するように実装してみる。

```scala:SimpleSearch.scala
    var matchIndexes = Seq[Int]()
    for (i <- 0 to text.length - 1) {
      val partText = text.slice(i, i + pattern.length)
      if (isMatch(partText, pattern)) matchIndexes = matchIndexes :+ i
    }
    matchIndexes
  }

  def isMatch(textPart: Seq[Char], pattern: Seq[Char]): Boolean = {
    var isMatch = true
    for (i <- 0 to pattern.length - 1) {
      if (textPart.length < pattern.length || textPart(i) != pattern(i)) isMatch = false
    }
    isMatch
  }

  println(s"出現場所: ${matchIndexes}")
}
```

以上のように実装する。

まず、

```scala
if (isMatch(partText, pattern)) matchIndexes = matchIndexes :+ i
```

ここでは、真偽値を返す `isMatch` 関数に切り出した「文書」と「パターン」を渡してマッチするかを確認する。
マッチしていた場合、その添字を加えたいので、

```scala
matchIndexes = matchIndexes :+ i
```

以上の処理で、シーケンスにパターンとマッチした添字を加える。

```scala
def isMatch(textPart: Seq[Char], pattern: Seq[Char]): Boolean = {
```

以上は、マッチするかを判定する `isMatch` 関数のインターフェース。
`textPart` と `pattern` はそれぞれ文字のシーケンスである Seq[Char] 型。
また、 Scala では真偽値を `Boolean` (ブーリアン)という型で宣言することができる。

```scala
var isMatch = true
```

これはループに入ってマッチしたかどうかを関数の戻り値として返す前に、デフォルトの値を `true` にしてしまう。
これでもし文字で不一致があった場合には、 `false` を代入するように利用する。

```scala
for (i <- 0 to pattern.length - 1) {
  if (textPart.length < pattern.length || textPart(i) != pattern(i)) isMatch = false
}
```

以上は、 0 から「パターン」の長さ - 1 までをループさせている。
`i` を添字に使い、もし、 `i` が切り出した「文書」の長さよりもパターンの文字数が大きくなる場合には、 `isMatch` を `false` にし、また、 `textPart` と `pattern` のその添字の文字が異なっても `false` にする。

ここでは、最初に切り出した「文書」の長さチェックをすることによって、もし

```scala
textPart.length < pattern.length
```

が true となる場合、 `textPart(i) != pattern(i)` は評価されず true として扱われるという、「 Scala の条件付き論理和の論理演算子　`||` 」の 特性を利用している。

なお、 Scala の論理演算子を以下にまとめる。

| 表現 | 名称 | 演算子 |
|:-:|:-:|:-:|
| A ではない | 否定 | ! |
| A または B | 条件付き論理和 | || |
| A かつ B | 条件付き論理積 | && |

これは JavaScript と全く同じ記号。

では、これで REPL で実行してみよう。

```scala:sbt
runMain SimpleSearch
```

以上を実行して、

```scala:sbt
[info] running SimpleSearch 
出現場所: List(8, 20)
[success] Total time: 1 s, completed 2021/07/27 12:22:07
```

このように成果の文字列が表示されれば成功。

# 【実習】正規表現を使った文字列検索

今回は非常にシンプルなアルゴリズムを使って、自分で文字列検索を実装した。
しかし、実際に Scala で非検索型の文字列検索を行う際には、 **正規表現** を使うのが一般的。

JavaScript でも正規表現を扱うクラスが存在したが、 Scala でも [Regex](https://www.scala-lang.org/files/archive/api/2.12.6/scala/util/matching/Regex.html) が存在する。

Regex を使うと、先ほどと同じ処理が以下のようにかけるので、実装してみよう。
`scala-study` フォルダに `RegexSearch.scala` というファイルを作成し、以下を記述する。

```scala:RegexSearch.scala
object RegexSearch extends App {
  val text = "カワカドカドカドドワンゴカドカドンゴドワドワンゴドワカワカドンゴドワ"
  val pattern = "ドワンゴ"
  val matchIndexes = pattern.r.findAllIn(text).matchData.map(_.start).toList
  println(s"出現場所: ${matchIndexes}")
}
```

sbt で `runMain RegexSearch` と実行すると、

```scala:sbt
[info] running RegexSearch 
出現場所: List(8, 20)
[success] Total time: 4 s, completed 2021/07/27 12:28:05
```

となり、マッチ箇所が分かる。

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

以上の呼び出しは非常に多くの呼び出しがグッと詰め込められているので、1つずつ説明していく。

Scala では、 String 型の r というメソッドを呼び出すことで、文字列を正規表現の Regex 型に変換できる。

`findAllIn` は、 Regex 型のメソッドで、与えられた正規表現にマッチする `Iterator` を取得できる。
戻り値は、 [MatchIterator](https://www.scala-lang.org/files/archive/api/2.12.6/scala/util/matching/Regex$.html#MatchIteratorextendsAbstractIterator%5BString%5DwithIterator%5BString%5DwithRegex.MatchData) という型になる。

次に、 MatchIterator の matchData フィールドは、マッチした文字列に対する様々な情報を与える Iterator[Match] 型を与える。
[Iterator](https://www.scala-lang.org/files/archive/api/2.12.6/scala/collection/Iterator.html) は、イテレータという何らかの要素の集合を巡回しながらアクセスできる型。
巡回可能なコレクションのような振る舞いを提供する。

また、 Iterator 型のメソッドを使ってアクセスできる、 [Match](https://www.scala-lang.org/files/archive/api/2.12.6/scala/util/matching/Regex$$Match.html) 型は、正規表現でマッチした情報となる。

以上の情報を使い、ここでは map 関数を用いて、 `_.start` で Match 型を start: Int というマッチした時の出現箇所のインデックスに変換している。
今まで map 関数には外部から関数を渡していたが、このように `_` アンダースコアを使うことで、 map 関数を適用しようとしてるコレクションの要素のメソッドも呼び出すことができる。
この map 関数を適用することで、 Iterator[Match] 型が Iterator[Int] 型に変換される。

そして最後に Iterator[Int] かたを toList 関数を呼び出して Seq として扱える List[Int] 型に変換する。

| プログラム | 説明 | 型 |
|:-:|:-:|:-:|
| pattern.r | String 型の pattern を Regex 型に変換する | Regex 型 |
| pattern.r.findAllIn(text) | text を検索し、 pattern にマッチする Iterator を取得する | MatchIterator 型 |
| pattern.r.findAllIn(text).matchData | マッチ情報を取得する ​| Iterator[Match] 型 |
| ppattern.r.findAllIn(text).matchData.map(_.start)	 | すべてのマッチ情報から出現箇所のインデックスを取得する | Iterator[Int] 型 |
| pattern.r.findAllIn(text).matchData.map(_.start).toList | Iterator[Int] 型を List[Int] 型に変換する | List[Int] 型 |

正規表現を使うと、20行弱近くかかっていた処理も1行で記述できるため、実際のプログラミングではこちらの方を使う機会の方が圧倒的に多いだろう。

# まとめ

* 文字列は String 型で表され、文字は Char 型で表される
* 検索には 索引型検索 と 非索引型検索 がある
* for や while を使ってループ処理を記述できる

# 挑戦

## 初級

* 文字列の中を検索して最初に見つかったインデックスを返すメソッド
    * indexOf(String str) メソッド
* 最後に見つかったインデックスを返すメソッド
    * lastIndexOf(String str) メソッド

```scala:sbt_console
scala>   val text = "カワカドカドカドドワンゴカドカドンゴドワドワンゴドワカワカドンゴドワ"
text: String = カワカドカドカドドワンゴカドカドンゴドワドワンゴドワカワカドンゴドワ

scala>   val pattern = "ドワンゴ"
pattern: String = ドワンゴ

scala> text.indexOf(pattern)
res1: Int = 8

scala> text.lastIndexOf(pattern)
res2: Int = 20
```

## 中級

```scala:SimpleSearch.scala
object SimpleSearch extends App {
  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) {
      val partText = text.slice(i, i + pattern.length)
      if (isMatch(partText, pattern)) matchIndexes = matchIndexes :+ i
    }
    matchIndexes
  }

  def isMatch(textPart: Seq[Char], pattern: Seq[Char]): Boolean = {
    var isMatch = true
    for (i <- 0 to pattern.length - 1) {
      if (textPart.length < pattern.length || textPart(i) != pattern(i)) {
        isMatch = false
        return isMatch
      }
      println(s"Processing: ${textPart}: ${i}")
    }
    isMatch
  }

  println(s"出現場所: ${matchIndexes}")
}
```

```scala:sbt
sbt:scala-study> runMain SimpleSearch
[info] compiling 1 Scala source to /Users/glaciermelt/workspace/scala-study/target/scala-2.12/classes ...
[info] running SimpleSearch 
Processing: 0
Processing: 0
Processing: 0
Processing: 0
Processing: 1
Processing: 2
Processing: 3
Processing: 0
Processing: 0
Processing: 0
Processing: 1
Processing: 0
Processing: 1
Processing: 2
Processing: 3
Processing: 0
Processing: 1
Processing: 0
出現場所: List(8, 20)
[success] Total time: 1 s, completed 2021/07/27 18:25:54
sbt:scala-study> runMain SimpleSearch
[info] compiling 1 Scala source to /Users/glaciermelt/workspace/scala-study/target/scala-2.12/classes ...
[info] running SimpleSearch 
Processing: ドカドカ: 0
Processing: ドカドド: 0
Processing: ドドワン: 0
Processing: ドワンゴ: 0
Processing: ドワンゴ: 1
Processing: ドワンゴ: 2
Processing: ドワンゴ: 3
Processing: ドカドン: 0
Processing: ドンゴド: 0
Processing: ドワドワ: 0
Processing: ドワドワ: 1
Processing: ドワンゴ: 0
Processing: ドワンゴ: 1
Processing: ドワンゴ: 2
Processing: ドワンゴ: 3
Processing: ドワカワ: 0
Processing: ドワカワ: 1
Processing: ドンゴド: 0
出現場所: List(8, 20)
```

## 上級

```scala:BMSearch.scala
object BMSearch extends App {
  val text = "カワカドカドカドドワンゴカドカドンゴドワドワンゴドワカワカドンゴドワ".toSeq
  val pattern = "ドワンゴ".toSeq
  val matchIndexes = search(text, pattern)

  /**
    * Boyer-Moore法を用いた非索引型の文字列検索
    *
    * @param text 検索対象のテキスト
    * @param pattern 検索文字列パターン
    * @return 一致文字のインデックス
    */
  def search(text: Seq[Char], pattern: Seq[Char]): Seq[Int] = {
    var matchIndexes = Seq[Int]()
    val skipTable = newSkipTable(pattern)
    var pt = pattern.length - 1 // textをなぞるポインタ

    while (pt < text.length) {
      var pp = pattern.length - 1 // patternをなぞるポインタ

      while (pp >= 0 && text(pt) == pattern(pp)) {
        if (pp == 0) matchIndexes = matchIndexes :+ pt
        pt -= 1
        pp -= 1
      }

      if (pp < 0) // パターンに一致した場合
        pt += pattern.length + 1
      else // 不一致文字がある場合
        pt += skipTable.getOrElse(text(pt), pattern.length)
    }
    matchIndexes
  }

  /**
    * textポインタの移動量をパターン文字ごとに計算する
    *
    * パターンに含まれない文字 -> pattern.length
    * パターンに含まれる文字 -> pattern.length - i - 1
    * 末尾文字 -> pattern.length
    * 同じ文字が含まれる場合 -> 最小のを優先
    *
    * @param pattern 検索文字列パターン移動量
    * @return 不一致文字の移動量Map
    */
  def newSkipTable(pattern: Seq[Char]): Map[Char, Int] = {
    pattern.init.zipWithIndex.map {
      case (c, i) => c -> (pattern.length - i - 1)
    }.toMap
  }

  println(s"出現場所: ${matchIndexes}")
}
```

```scala:sbt
sbt:scala-study> runMain BMSearch
[info] compiling 1 Scala source to /Users/glaciermelt/workspace/scala-study/target/scala-2.12/classes ...
[info] running BMSearch 
出現場所: List(8, 20)
[success] Total time: 5 s, completed 2021/07/27 21:37:14
```