【Go】String pattern matching algorithms (文字列探索アルゴリズム)

# Goでプログラミングの基礎を学ぶシリーズ
スクールでは教えてくれないプログラミングの基礎、**データ構造とアルゴリズム**をGoで学んでいくシリーズです。
そのデータ構造がどのようなものであるかは、理解を助けてくれるサイトを紹介しつつ、簡単な説明に留めさせていただきます。(ご自身でも調べてみてください！)
筆者自身、Exerciseに取り組みながら理解を深めていったので、コードの解説を中心に記事を書いていきたいと思います。

|  | タイトル |
|------|---------|
| #0 | [はじめに (環境構築と勉強方法)](https://qiita.com/miyyuk/items/0b959774a2e436f087c0) |
| #1 | [Pointer, Array, String (ポインタと配列と文字列と)](https://qiita.com/miyyuk/items/75fad6c02b76354fa49d) |
| #2 | [File operations (ファイル操作)](https://qiita.com/miyyuk/items/641faf682e09709727af) |
| #3 | [Linked List (連結リスト)](https://qiita.com/miyyuk/items/af9d3352f89f11365dc4) |
| #4 | [Stack & Queue (スタックとキュー)](https://qiita.com/miyyuk/items/a188def21c31367330f3) |
| #5 | [Search algorithms (探索アルゴリズム)](https://qiita.com/miyyuk/items/91920dee5151e9c4c43e) |
| #6 | [Tree (木構造)](https://qiita.com/miyyuk/items/a11c22a62bb95c1996ba) |
| #7 | [Sorting algorithms (ソートアルゴリズム)](https://qiita.com/miyyuk/items/85c2ed8176e9bdf7e677)|
| #8 | String pattern matching algorithms (文字列探索アルゴリズム) **☜ here** |

最終回となる今回は**#8 String pattern matching algorithms (文字列探索アルゴリズム)**です。

# String pattern matching とは
文字列探索とは、ある文字列の中から、別のある文字列を探索することであり、さまざまなアルゴリズムがあります。
ここでは中でも代表的な文字列探索のアルゴリズムの Go での実装例をみていきます。

## Naive algorithm (ナイーブ法)
`ナイーブ法`は、`Brute Force algorithm (力まかせ探索)` とも呼ばれます。
文字列( `text` )と探索文字列( `pattern` )を先頭から1文字ずつ探索し、不一致があった場合は探索文字列を1文字だけずらして、再度探索文字列の先頭から1文字ずつ探索していくアルゴリズムです。
文字列の長さを `n`, 探索文字列の長さを `m` としたときの時間計算量は $O(mn)$ ですが、これは文字列および探索文字列のなかで、同じ文字が何度も続く場合の計算量になりますので、実質はほぼ $O(n)$ となるようです。

https://algoful.com/Archive/Algorithm/BrouteForceSearch

```golang
func NaiveSearch(txt, pat string) {
	if len(txt) <= len(pat) {
		fmt.Println("text is shorter than pattern!")
	}

	patLastIndex := len(pat) - 1 // pattern の最後の index
	var idx []int                // pattern と一致した text 部分の先頭の index を格納する slice
	for i := 0; i < len(txt)-patLastIndex; i++ {
		for j := 0; j < len(pat); j++ {
			if txt[i+j] != pat[j] {
				break // 文字が一致しないとき、 i を一つ進める
			}
			if j == patLastIndex { // pattern がすべて一致したとき
				idx = append(idx, i)
			}
		}
	}

	if len(idx) != 0 {
		fmt.Printf("match index: %v\n", idx)
	} else {
		fmt.Println("no matching index!")
	}
}

func main() {
	NaiveSearch("xyzzxzyxyxyyzxzyyxyxyyz", "xyxyy")
}
```
☟ 出力結果

```
match index: [7 17]
```

## Knuth-Morris-Pratt algorithm (KMP法)
`KMP法` (クヌース・モリス・プラット法)は、探索文字列の先頭から探索していくのは `ナイーブ法` と同様ですが、余計な探索を避けるための工夫がなされています。
文字列の長さを `n`, 探索文字列の長さを `m` としたときの時間計算量は $O(n)$ となりますが、実装は少々複雑になります。
詳細は以下サイトをご参考ください。

https://algoful.com/Archive/Algorithm/KMPSearch

```golang
func KMPSearch(txt, pat string) {
	if len(txt) < len(pat) {
		fmt.Println("text is shorter than pattern!")
	}

	// スライドする文字数を決める ずらし表 を作成(pattern に対して pattern 自身を比較する)
	table := make([]int, len(pat))
	table[0] = 0
	for i, j := 1, 0; i < len(pat); { // j は pattern 自身の比較で直前までに一致していた文字数
		if pat[i] == pat[j] { // 一致している場合
			j++
			table[i] = j
			i++
		} else { // 一致しない場合
			if j != 0 {
				j = table[j-1]
			} else {
				table[i] = 0
				i++
			}
		}
	}
	fmt.Printf("table: %v\n", table)

	var idx []int // pattern と一致した text 部分の先頭の index を格納する slice
	for i, j := 0, 0; i < len(txt); {
		if txt[i] == pat[j] { // 文字が一致している場合
			j++
			i++
			if j == len(pat) { // pattern がすべて一致したとき
				idx = append(idx, i-j)
				j = table[j-1]
			}
		} else { // 文字が一致しない場合
			if j != 0 {
				j = table[j-1]
			} else {
				i++
			}
		}
	}

	if len(idx) != 0 {
		fmt.Printf("match index: %v\n", idx)
	} else {
		fmt.Println("no matching index!")
	}
}

func main() {
	KMPSearch("xyzzxzyxyxyyzxzyyxyxyyz", "xyxyy")
}
```
☟ 出力結果

```
table: [0 0 1 2 0]
match index: [7 17]
```

## Boyer-Moore algorithm (BM法)
`BM法` (ボイヤー・ムーア法)は、ナイーブ法やKMP法と異なり、探索文字列の後方から探索していくアルゴリズムです。
`KMP法` と同様に、余計な探索を避けるために工夫されています。
文字列の長さを `n`, 探索文字列の長さを `m` としたときの時間計算量は、最良の場合で $O(n/m)$, 最悪の場合で $O(mn)$ となります。
しかし、 `ナイーブ法` と同様に、最悪の場合というのは、これは文字列および探索文字列のなかで、同じ文字が何度も続く場合になりますので、実用する上では、`ナイーブ法`, `KMP法` よりも高速なアルゴリズムのようです。
詳細は以下サイトをご参考ください。

https://algoful.com/Archive/Algorithm/BMSearch

```golang
func BMSearch(txt, pat string) {
	if len(txt) < len(pat) {
		fmt.Println("text is shorter than pattern!")
	}

	patLastIndex := len(pat) - 1 // pattern の最後の index

	// スライドする文字数を決める ずらし表 を作成
	table := make(map[byte]int)
	for i, j := patLastIndex, 0; i >= 0; i, j = i-1, j+1 { // j は pattern の末尾からの文字数
		if _, ok := table[pat[i]]; !ok { // pattern に含まれる文字でまだ table に存在しない場合
			table[pat[i]] = j
		}
	}
	fmt.Printf("table: %v\n", table)
	for key, value := range table {
		fmt.Printf("key: %s value: %v\n", string(key), value)
	}

	var idx []int // pattern と一致した text 部分の先頭の index を格納する slice
	for i := patLastIndex; i < len(txt); {
		// pattern の後方から探索を行う
		for j := 0; j < len(pat); j++ { // j は pattern の末尾からの文字数
			// 文字が一致している場合
			if txt[i-j] == pat[patLastIndex-j] {
				if j == patLastIndex { // pattern がすべて一致したとき
					idx = append(idx, i-j)
				} else {
					continue
				}
			}

			// 文字が一致しない場合 または pattern がすべて一致した場合、比較位置をずらす
			slide, ok := table[txt[i-j]] // スライドする文字数を table から取得
			if !ok {                     // 比較している text の文字が pattern の中にない場合
				slide = len(pat)
			}
			// スライドする文字数を求める
			if slide-j > 0 {
				i += slide - j
			} else { // 現在の位置より前にスライドしてしまう場合
				i++ // 1 だけスライドする
			}
			break // j++ しても文字が一致することはないので break
		}
	}

	if len(idx) != 0 {
		fmt.Printf("match index: %v\n", idx)
	} else {
		fmt.Println("no matching index!")
	}
}

func main() {
	BMSearch("xyzzxzyxyxyyzxzyyxyxyyz", "xyxyy")
}
```
☟ 出力結果

```
table: map[120:2 121:0]
key: y value: 0
key: x value: 2
match index: [7 17]
```


# おわりに
Exerciseの解答例はあくまで例なので、もっといい書き方あるよ！という方、ぜひコメントをお寄せください！
説明についても、筆者自身が初心者であるため、ご指摘や補足は大歓迎でございます。

株式会社Link Sportsでは、あらゆるスポーツを楽しむ人たちに送る、チームマネジメントアプリを開発しています。
未経験でも経験豊富なエンジニアの方でも、スポーツ好きなら活躍できる環境があります！
絶賛エンジニア募集中です！
Wantedly ▶︎ https://www.wantedly.com/projects/324177
Green ▶︎ https://www.green-japan.com/job/82003

データ構造とアルゴリズムを `Go` での実装例とともに学習してきましたが、いかがでしたか？
プログラミングスクールでは、全体像を掴むためにフレームワークを用いて簡単なアプリを作ったりすることと思いますが、いざ就職してみると、思うようにコードが書けない！なんてことになりませんでしたか？
筆者自身は、データ構造とアルゴリズムを学習してからのほうが、格段にコードが書きやすくなりました。
このシリーズがプログラミング初心者の方の助けになれば幸いです。