BohYoh.comトップページへ

Javaによるアルゴリズムとデータ構造

戻る  

演習8-4の解答

 演習8-1(p.243)と同様に、Boyer-Moore法による探索過程の詳細を表示するプログラムを作成せよ。

// 演習8-4 // Boyer-Moore法による文字列探索(照合過程の詳細を表示) import java.util.Scanner; class BMmatch {     //--- Boyer-Moore法による文字列探索 ---//     static int bmMatch(String txt, String pat) {         int pt;                                    // txtをなぞるカーソル         int pp;                                    // patをなぞるカーソル         int txt_len = txt.length();                // txtの文字数         int pat_len = pat.length();                // patの文字数         int[] skip = new int[Character.MAX_VALUE + 1];    // スキップテーブル         int count = 0;    // 比較回数         int k = -1;         // スキップテーブルの作成         for (pt = 0; pt <= Character.MAX_VALUE; pt++)             skip[pt= pat_len;         for (pt = 0; pt < pat_len - 1; pt++)             skip[pat.charAt(pt)] = pat_len - pt - 1;                                                 // pt == pat_len - 1である         // 探索         while (pt < txt_len) {             pp = pat_len - 1;                    // patの最後の文字に着目             if (k == pt - pp)                 System.out.print("    ");             else {                 System.out.printf("%2d  ", pt - pp);                 k = pt - pp;                          for (int i = 0; i < txt.length(); i++)                 System.out.print(txt.charAt(i" ");             System.out.println();             for (int i = 0; i < pt * 4; i++)                 System.out.print(" ");             System.out.print(txt.charAt(pt== pat.charAt(pp'+' '|');             System.out.println();             for (int i = 0; i < (pt-pp4; i++)                 System.out.print(" ");             for (int i = 0; i < pat.length(); i++)                 System.out.print(pat.charAt(i" ");             System.out.println();             System.out.println();             count++;             while (txt.charAt(pt== pat.charAt(pp)) {                 if (pp == 0)                     return pt;            // 探索成功                 pp--;                 pt--;                 if (k == pt - pp)                     System.out.print("    ");                 else {                     System.out.printf("%2d  ", pt - pp);                     k = pt - pp;                                  for (int i = 0; i < txt.length(); i++)                     System.out.print(txt.charAt(i" ");                 System.out.println();                 for (int i = 0; i < pt * 4; i++)                     System.out.print(" ");                 System.out.print(txt.charAt(pt== pat.charAt(pp'+' '|');                 System.out.println();                 for (int i = 0; i < (pt-pp4; i++)                     System.out.print(" ");                 for (int i = 0; i < pat.length(); i++)                     System.out.print(pat.charAt(i" ");                 System.out.println();                 System.out.println();                 count++;             }             pt += skip[txt.charAt(pt)];         }         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 = bmMatch(s1, s2);    // 文字列s1から文字列s2をBM法で探索         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);         }     } }


戻る