Javaで学ぶアルゴリズム -文字列探索（KMP法）

文字列探索（KMP法）

クヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列）Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。

• 力任せ法とは違い、それまでの照合結果を活用する
• 複雑だけど Boyer-Moore法 と同等の性能なのであんまり使われないらしい

実行環境

• JUnit 5
• Java 8

テストコード

KmpSearchTest.java

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.junit.jupiter.api.Assertions.assertThrows;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Test;

public class KmpSearchTest {

	private String text;

	@BeforeEach
	void setUp() {
		text = "これはテストです。This is a test. もう一度テストします。";
	}

	@DisplayName("パターンがテキスト内に存在する場合")
	@Nested
	class PatternExists {

		@DisplayName("パターンがテキストの最初に存在する場合、0が返ること")
		@Test
		void testPatternExistsAtBeginning() {
			assertThat(KmpSearch.kmpSearch(text, "これ"), is(0));
		}

		@DisplayName("パターンがテキストの中間に存在する場合、その位置が返ること")
		@Test
		void testPatternExistsInMiddle() {
			assertThat(KmpSearch.kmpSearch(text, "test"), is(19));
		}

		@DisplayName("パターンがテキストの最後に存在する場合、その位置が返ること")
		@Test
		void testPatternExistsAtEnd() {
			assertThat(KmpSearch.kmpSearch(text, "します"), is(32));
		}

		@DisplayName("パターンがテキストに複数存在する場合、最初の位置を返すこと")
		@Test
		public void testPatternExistsMultipleTimes() {
			assertThat(KmpSearch.kmpSearch(text, "テスト"), is(3));
		}

		@DisplayName("パターンが空の場合、0が返ること")
		@Test
		void testPatternIsEmpty() {
			assertThat(KmpSearch.kmpSearch(text, ""), is(0));
		}

		@DisplayName("テキストとパターンが共に空の場合、0が返ること")
		@Test
		void testBothTextAndPatternEmpty() {
			assertThat(KmpSearch.kmpSearch("", ""), is(0));
		}
	}

	@DisplayName("パターンがテキスト内に存在しない場合")
	@Nested
	class PatternNotExists {
		@DisplayName("パターンがテキストに存在しない場合、-1が返ること")
		@Test
		void testPatternNotExists() {
			assertThat(KmpSearch.kmpSearch(text, "成功"), is(-1));
		}

		@DisplayName("パターンの文字列の長さがテキストよりも大きい場合、-1が返ること")
		@Test
		void testPatternLongerThanText() {
			String longPattern = "これはテストです。This is a test. もう一度テストします。失敗";
			assertThat(KmpSearch.kmpSearch(text, longPattern), is(-1));
		}

		@DisplayName("テキストが空の場合、-1が返ること")
		@Test
		void testTextIsEmpty() {
			assertThat(KmpSearch.kmpSearch("", "テスト"), is(-1));
		}
	}

	@DisplayName("例外が投げられる場合")
	@Nested
	class ExceptionThrown {
		@DisplayName("渡されるパターンがnullの場合、NPEが投げられること")
		@Test
		void testPatternIsNull() {
			assertThrows(NullPointerException.class, () -> {
				KmpSearch.kmpSearch(text, null);
			});
		}

		@DisplayName("渡されるテキストがnullの場合、NPEが投げられること")
		@Test
		void testTextIsNull() {
			assertThrows(NullPointerException.class, () -> {
				KmpSearch.kmpSearch(null, "テスト");
			});
		}
	}
}

文字列探索（KMP法）アルゴリズム

KmpSearch.java

public class KmpSearch {

	/**
	 * KMPアルゴリズムを使用して、指定されたテキスト内で指定されたパターンを探す。
	 *
	 * @param text 検索対象のテキスト
	 * @param pattern 検索したいパターン
	 * @return パターンがテキスト内で最初に出現する開始インデックス
	 * @throws NullPointerException textまたはpatternがnullである場合
	 */
	public static int kmpSearch(String text, String pattern) {

		if (pattern.isEmpty()) {
			return 0;
		}

		int textIndex = 1;
		int patternIndex = 0;
		int[] skipTable = new int[pattern.length() + 1];

		// スキップテーブルの作成
		// テーブル内では、各位置に対応する部分一致の長さ情報を保持
		skipTable[textIndex] = 0;
		while (textIndex != pattern.length()) {
			if (pattern.charAt(textIndex) == pattern.charAt(patternIndex)) {
				skipTable[++textIndex] = ++patternIndex;
			} else if (patternIndex == 0) {
				skipTable[++textIndex] = patternIndex;
			} else {
				patternIndex = skipTable[patternIndex];
			}
		}

		// テキスト内でパターンを探索
		textIndex = patternIndex = 0;
		while (textIndex != text.length() && patternIndex != pattern.length()) {
			if (text.charAt(textIndex) == pattern.charAt(patternIndex)) {
				textIndex++;
				patternIndex++;
			} else if (patternIndex == 0) {
				textIndex++;
			} else {
				patternIndex = skipTable[patternIndex];
			}
		}

		// パターンが見つかった場合、その開始位置を返す
		if (patternIndex == pattern.length()) {
			return textIndex - patternIndex;
		}
		return -1;
	}
}