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

文字列探索（力任せ法）

力まかせ探索（ちからまかせたんさく、英: Brute-force search）またはしらみつぶし探索（英: Exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。

線形探索を拡張したアルゴリズムになるので、素朴法とか単純法とかとも呼ばれたりするようです。

実行環境

• JUnit 5
• Java 8

テストコード

BruteForceSearchTest.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 BruteForceSearchTest {

	private String text;

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

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

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

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

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

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

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

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

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

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

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

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

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

文字列探索（力任せ法）アルゴリズム

BruteForceSearch.java

public class BruteForceSearch {

	/**
	 * 力任せ法を用いて、テキスト文字列内でパターン文字列が最初に出現する箇所を探す
	 * @param text 検索対象のテキスト
	 * @param pattern 検索したいパターン
	 * @return パターンがテキスト内で最初に出現する開始インデックス（見つからない場合は-1）
	 */
	public static int bruteForceSearch(String text, String pattern) {
		int textIndex = 0;
		int patternIndex = 0;

		while (textIndex != text.length() && patternIndex != pattern.length()) {
			if (text.charAt(textIndex) == pattern.charAt(patternIndex)) {
				// 文字が一致する場合、次の位置を比較
				textIndex++;
				patternIndex++;
			} else {
				// 不一致の場合、テキストのインデックスを右にシフト
				textIndex = textIndex - patternIndex + 1;
				patternIndex = 0;
			}
		}
		if (patternIndex == pattern.length()) {
			return textIndex - patternIndex;
		}
		return -1;
	}
}