【Java】KMP法

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。

ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。

【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧

KMP法

package chap07;

import java.util.Scanner;

public class KnuthMorrisPatternMatch {
	
	//--- KMP法による文字列探索 ---//
	static int kmpMatch(String text, String pattern) {
		
		int   pt   = 1;    // textをなぞるカーソル（ポインタ）
		int   pp   = 0;    // patternをなぞるカーソル（ポインタ）
		int[] skip = new int[pattern.length() + 1];
		                   // スキップテーブル
		
		//--- スキップテーブル（再開値の表）の作成 ---//
		skip[pt] = 0;
		
		// ptがpatternの長さになるまで繰り返す
		while (pt != pattern.length()) {
			
			// テキストの文字とパターンの文字が一致するとき
			if (pattern.charAt(pt) == pattern.charAt(pp)) {
				
				skip[++pt] = ++pp;
			
			// 文字が一致せず、ppが0のとき
			} else if (pp == 0) {
				
				skip[++pt] = pp;
			
			} else {
				
				pp = skip[pp];
			}
		}
		
		//--- 探索 ---//
		pp = 0;
		pt = pp;
		// pt = pp = 0と同義
		
		while (pt != text.length() && pp != pattern.length()) {
			
			// テキストの文字とパターンの文字が一致するとき
			if (text.charAt(pt) == pattern.charAt(pp)) {
				pt++;
				pp++;
			} else if (pp == 0) {
				pt++;
			} else {
				pp = skip[pp];
			}
		}
		
		if (pp == pattern.length()) {
			return pt - pp;
		}
		
		return -1;
		
	}
	
	
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		// テキスト用文字列
		System.out.print("テキスト：");
		String s1 = stdIn.next();
		
		// パターン用文字列
		System.out.print("パターン：");
		String s2 = stdIn.next();
		
		// 文字列s1から文字列s2を探索
		int idx = kmpMatch(s1, s2);
		
		if (idx == -1) {
			System.out.println("テキスト中にパターンは存在しません。");
		} else {
			
			// マッチ文字の直前までの半角での文字数を求める
			int len = 0;
			
			for (int i = 0; i < idx; i++) {
				len += s1.substring(i, i + 1).getBytes().length;
			}
			
			len += s2.length();
			
			System.out.println((idx + 1) + "文字列にマッチします。");
			System.out.println("テキスト：" + s1);
			System.out.printf(String.format("パターン：%%%ds\n", len), s2);
		}
	}

}

学習内容まとめ

eclipse操作時に役立つショートカットまとめ
https://qiita.com/toshi0383/items/1d2a990392998789062c

$\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}$
ご協力のほどよろしくお願いします。