【Java アルゴリズム修行⑰】文字列探索 ~KMP法~

### KMP法とは

[前回](https://qiita.com/kotaito/items/d1c3f84409d1527814c4)の力まかせ法では、不一致の文字に出会った場合、
パターンを移動して、パターンの先頭からテキストとの照合を行なっていましたが、
**移動の度に照合結果が先頭に戻ってしまうので、その点は非効率であるといえます。**
**そんな非効率な部分を有効活用したのがこのKMP法らしいです。**

`ZABCABXACCAD`　というテキストから `ABCABD`というパターンを探索するとして、
まず最初はテキストとパターンの先頭文字から順に照合を行います。
![スクリーンショット 2021-05-17 15.27.54.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/036aed5c-0269-5418-dfc0-c7c7a1f44143.png)
テキストの先頭文字 `Z`は、パターンには含まれない文字なので、不一致として、パターンを1文字進めます。
![スクリーンショット 2021-05-17 15.26.30.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/a17171ab-bb3b-2389-99c2-ee4fc042e5d1.png)
パターンの先頭から順に照合していくと、パターンの末尾文字`D`がテキスト`X`と一致しません。

ここで改めて文字列を見てみると、テキスト側の`AB`と、パターンの先頭にある`AB`が一致していることが分かります。
力まかせであれば、そのままパターンを1文字進めるだけですが、
このAB部分を`照合済`とみなせれば テキスト側の`X`以降の部分から、
パターンの`CABD`と一致するかを調べれば良いことになります。
![スクリーンショット 2021-05-17 15.29.00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/bdde7a4c-1bef-1814-e2f5-466f36bd859c.png)
そこで、次のように`AB`が重なるようパターンを一気に3文字ズラすと、
パターンの3文字目である`C`からテキストとの照合を開始することができます。
![スクリーンショット 2021-05-17 15.29.53.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/6f0a2a79-251c-fec8-993d-bbe958f60f13.png)
このように、**KMP法はテキストとパターン中の重なっている部分をうまく見つけ出し、 
照合を再開する位置を求め、パターンの移動をなるべく大きくしようというアルゴリズムだそうです。**

何文字目から照合を再開するのかを、パターンを移動するたびに計算し直していると、高い効率は望めないので
その値を事前に<表>として作成しておけば、照合結果によってズラす文字数を決めることができます。

この表の作成にあたっては、パターン内の ”重複した文字の並び”を見付ける必要があります。

もし、パターンの1文字目が不一致の場合、
パターンを1文字ずらして先頭文字から照合を合わせなければならないのは自明なので、
パターンがテキストの2文字目以降に移動した時を考えていきます。
  また、パターン内で同じ文字列があった場合の移動なので、パターン同士を重ね合わせて計算します。

まずはパターン`ABCAD`同士を1文字ずらして重ね合わせてみましょう。
![スクリーンショット 2021-05-17 15.33.50.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/c5d6796a-abce-a138-ed51-bb7ff093744f.png)

この時点で、青文字部分に重なりはないので、
もしパターンの2文字目がテキストと不一致だった場合は、
パターンの頭から照合を再開しなければいけないことが分かるので 、2文字目`B`の再開値を0とします  。
この再開値は、パターンの1文字目のインデックスが0であり、その位置から照合を再開するという見方になります。

![スクリーンショット 2021-05-17 15.35.37.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/25a0ee93-ccb4-ae83-a20e-24d075374633.png)
またパターンを1文字ズラします。
![スクリーンショット 2021-05-17 15.37.59.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/75f8b910-99cf-5543-497e-87156ec58f6b.png)
やはり文字は一致しないので、3文字目`C`の再開値も0となります。
![スクリーンショット 2021-05-17 15.38.22.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/63f7ee1b-aed3-d164-9312-bb03d53d71f3.png)
もう1文字ずららしたところで初めて`AB`が一致し他ので、次のことが分かります。
![スクリーンショット 2021-05-17 15.40.00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/a02ff894-395e-b749-f609-4e8376b62741.png)

* もし、パターンの4文字目の`A`まで一致していれば、パターン移動後に`A`をスキップして  2文字目から照合できる
* もし、パターンの5文字目の`B`も一致してれば、パターン移動後に`AB`をスキップして3文字目から照合できる

そこで、これらの文字の再開値は、パターンの配列上インデックスでは 1 と 2ということになります 。
`A`が一致していれば、 `B`からなので、1　　`AB`が一致していれば、`C`からなので 2 　ということです。
![スクリーンショット 2021-05-17 15.41.51.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/570b3eb2-79f1-3a0d-4a88-4392b201aac7.png)
最後の`D`と比べてみると、ここでは一致しないので、末尾文字の再開値は0となります。
![スクリーンショット 2021-05-17 15.43.26.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/e7425b0b-7b66-04e0-18f4-4a558971f0c9.png)
![スクリーンショット 2021-05-17 15.43.09.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/774179b8-0c87-adeb-e11b-743d76c947f4.png)
つまり、パターンの文字列の中に、同じ文字列が含まれていた場合、(`ABCABD`のように`AB`が2つある場合)
テキスト内のカーソルをスキップさせることができるので、そこで何文字スキップするのかという表を作成することができました。


###コードに落とし込んでみる

```java:KMP.java
static int kmpMatch(String target, String pat) {
		int pt = 1;								// targetをなぞるカーソル
		int pp = 0;							    // patをなぞるカーソル
		int[] skip = new int[pat.length() + 1];	// スキップテーブル

		// スキップテーブルの作成
		skip[pt] = 0;
		while (pt != pat.length()) {
		  System.out.println(pt + "," + pp);
		  if (pat.charAt(pt) == pat.charAt(pp)) {
			skip[++pt] = ++pp;
		  } else if (pp == 0) {
			skip[++pt] = pp;
		  } else {
			pp = skip[pp];
		  }
			for(int a : skip)
				System.out.print(a + ",");
			System.out.println();

		}

```

`KmpMatchメソッド`が受け取る引数や返り値は、力まかせ法の関数`bfMatch`と変わりません。
最初にスキップテーブルを作成し、その後探索を行うという流れになります。
 
スキップテーブルの作成は
まず、patの長さ + 1のテーブルを作成し、ptは1 ppは0として、ずらして比較できるようにしています。

最初は`if (pat.charAt(pt) == pat.charAt(pp)) `にて 1文字ずらした状態で照合を行い、
一致していれば、1,2,3とインクリメントした値を追加、
不一致であり、パターンの1文字目であればそのまま0を代入（パターンの最初から）
不一致であり、カーソルがパターンの2文字目以降であった場合、表の値をそのままパターンのカーソルに代入するという流れです。

`ABAABDC`というパターンで実際に流れを追っていきましょう。
![スクリーンショット 2021-05-17 15.51.11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/7dfe28e2-4ab0-6055-39ee-52e1a00941f9.png)
1文字ズラしだけでは不一致なので、ppは0となり、表に0を代入し、ptは前置インクリメントして2となります。
![スクリーンショット 2021-05-17 15.52.27.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/8ad1d2c7-d39e-3b8f-3d34-a0f947105bc3.png)
3文字目のAと一致したので、skip[3]に 1を代入し、pt 3 pp 1で比較します。 
![スクリーンショット 2021-05-17 15.52.41.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/338e0949-09b4-05f2-09b8-ec46d9365a2d.png)
ここは不一致ですが、ppは1なので、 skip[1]の値である 0を ppに代入し、pt 3 pp 0で比較します。
![スクリーンショット 2021-05-17 15.53.14.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/3a0b4b6f-01ed-3b20-acf2-74d1c3c66ed9.png)
一致したので、skip[4]に 1を代入し、（ppを前置インクリメント）pt 4 pp 1で比較します。 
![スクリーンショット 2021-05-17 15.54.46.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/b68a41fb-ddf4-e412-8077-cdf8f50a5f1f.png)
一致したので、skip[5]に 2を代入し、pt5 pp 2で比較します。
![スクリーンショット 2021-05-17 15.55.03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/6317b44b-0399-62df-ff4a-0acb0b9e5504.png)
不一致で、ppは2なので、skip[2]の0を ppに代入し、pt 5 pp 0で比較します。
![スクリーンショット 2021-05-17 15.55.40.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/6d11f919-008c-5110-b3ca-dfc5f39cc3b5.png)
不一致で ppは0なので、表に0を代入し、ptは6 ppは0で比較します。
![スクリーンショット 2021-05-17 15.55.48.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/a483b111-e051-0846-ca23-c02f8111722c.png)
不一致でppは0なので、表に0を代入した時点で、表が完成します。

![スクリーンショット 2021-05-17 15.56.19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/3ed0a1b9-1b0c-b622-5fed-427cd409858c.png)

この表を見る限り、
もし`ABA`or`ABAA`まで一致していれば、先頭のAをスキップして、2文字目の`B`から
`ABAAB`まで一致してれば、 先頭の`AB`をスキップして3文字目の`A`から探索を再開すればいいということになります。
ここまで表がわかれば、あとは同様に探索を行うだけです。

```java:KMP.java
		// 探索
		pt = pp = 0;
		while (pt != target.length() && pp != pat.length()){
			if (target.charAt(pt) == pat.charAt(pp)) {
				pt++;
				pp++;
			} else if (pp == 0)
				pt++;
			else
				pp = skip[pp];
		}

		if (pp == pat.length())		// パターンの全文字を照合
			return pt - pp;
		return -1;     	         	// 探索失敗
     }
```

一致していればターゲットも、パターンのカーソルも1個ずつ進め、
不一致かつ、パターンの1文字目で不一致であれば、ターゲットのカーソルだけを1個進める。
不一致かつ、パターンの2文字目以降であれば、パターンのカーソルを表に合わせて進めるという流れになります。

このように、**KMP法では、テキストを走査するカーソルptは前進するだけで後退することはありません。**
** プログラム自体は複雑ですが、Boyer-Moore法と同等以下の性能しか発揮できない**ので、それほど利用されないらしいです汗


###学んだこと

*  パターン内に同様の文字列があった場合、照合カーソルをいちいち後退させる必要がなくなるのがKMPの特徴
*  パターン内に繰り返される文字がなければ、あまり効果がないのも事実。

パターン内に繰り返しがあれば、一致した位置によっては無駄な照合をする必要がなくなる
という方法はなるほどと思いましたが、実際に探索するパターンに都合よく繰り返しがあるとも限らないので
そういう考え方もあるよということで、引き続き頑張っていきます！