明解 Javaによるアルゴリズムとデータ構造 8-1_力まかせ法

8-1 力まかせ法

  • brute force な文字列探索やるよ~

順探索

ソースコード

  • ちょっと焦げ臭い。もっとスマートに書けそうだが・・・
  • 進捗表示が意外とめんどかった。
    • 探索対象文字列の何文字目から探索しているかを表示する部分で、フラグ処理が必要なんだが、ここをうまくかければ、綺麗になりそう。
import java.util.Scanner;

class BFmatch {
    static int bfMatch(String txt, String pat) {
        // 探索対象文字列のインデックス
        int pt = 0;
        // マッチャーのインデックス
        int pp = 0;
        
        // 進捗表示インデックスたち・・・
        // 「部分一致状時マッチャー用スペーサー」生成のためのインデックス
        int pFixed = -1;
        // 「マッチャー用スペーサー」生成のためのインデックス
        int patIndex = 0;
        // 「比較対象識別子用スペーサー」生成のためのインデックス
        int charIndex = 0;

        // スペーサーたち・・・
        final String txtSpacer = "%4s";
        String patSpacer;
        String charSpacer;
        
        // 文字比較回数
        int compareCnt = 0;
        
        // ブルートフォースサーチ
        while (pt != txt.length() && pp != pat.length()) {
            if (pFixed > 0) {
                patIndex = pFixed;
            } else {
                patIndex = pt;
            }
            patSpacer = (patIndex != 0) ? "%" + patIndex + "s" : "";
            charIndex = patIndex + pp;
            charSpacer = (charIndex != 0) ? "%" + charIndex + "s" : "";

            // 単一文字一致
            if (txt.charAt(pt) == pat.charAt(pp)) {
                if (pFixed < 0) {
                    System.out.printf("%3s " + txt + "\n", pt);
                    pFixed = pt;
                } else {
                    System.out.printf(txtSpacer + txt + "\n", "");
                }
                System.out.printf(txtSpacer + charSpacer + "+\n", "", "");
                System.out.printf(txtSpacer + patSpacer + pat + "\n\n", "", "");
                pt++;
                pp++;
                
            // 単一文字不一致
            } else {
                if (pFixed < 0) {
                    System.out.printf("%3s " + txt + "\n", pt);
                    pFixed = pt;
                } else {
                    System.out.printf(txtSpacer + txt + "\n", "");
                }
                System.out.printf(txtSpacer + charSpacer + "|\n", "", "");
                System.out.printf(txtSpacer + patSpacer + pat + "\n\n", "", "");
                pt = pt - pp + 1;
                pp = 0;
                pFixed = -1;
            }
        }
        
        // 探索成功
        if (pp == pat.length()) {
            System.out.println("比較回数: " + compareCnt);
            return pt - pp;
        }
        
        // 探索失敗
        System.out.println("比較回数: " + compareCnt);
        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();

        int idx = bfMatch(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);
        }
    }
}

逆探索

  • とりあえず後回し

String.indexOf による文字列探索

  • int indexOf(String str)
  • int indexOf(String str, int fromIndex)
    • fromIndex 以降を検索
  • int lastIndexOf(String str)
  • int lastIndexOf(String str, int fromIndex)
    • fromIndex 以降を検索