新・明解Javaで学ぶアルゴリズムとデータ構造

演習8-1の解答

0 ABABCDEFGHA
  +
  ABC

  ABABCDEFGHA
   +
  ABC

  ABABCDEFGHA
    |
  ABC

1 ABABCDEFGHA
   |
   ABC
…中略…
比較は7回でした。

　右のように、力まかせ法の探索過程を詳細に表示するプログラムを作成せよ。
　パターンを移動するたびに、照合するテキスト側の先頭文字のインデックスを表示すること。
　また、照合過程では、比較する二つの文字間に、一致すれば文字'+'を、一致しなければ文字'|'を表示すること。
　なお、文字を比較した総回数を最後に表示すること。

// 演習8-1
// 力まかせ法による文字列探索（照合過程の詳細を表示）

import java.util.Scanner;

class BFmatchEx {

   //--- 力まかせ法による文字列探索 ---//
   static int bfMatch(String txt, String pat) {
      int pt = 0;      // txtをなぞるカーソル
      int pp = 0;      // patをなぞるカーソル
      int count = 0;   // 比較回数
      int k = -1;

      while (pt != txt.length() && pp != pat.length()) {
         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 * 2 + 4; i++)
            System.out.print(" ");
         System.out.print(txt.charAt(pt) == pat.charAt(pp) ? '+' : '|');
         System.out.println();

         for (int i = 0; i < (pt-pp) * 2 + 4; 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++;

         if (txt.charAt(pt) == pat.charAt(pp)) {
            pt++;
            pp++;
         } else {
            pt = pt - pp + 1;
            pp = 0;
         }
      }
      System.out.printf("比較は%d回でした。\n", count);
      if (pp == pat.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();               // パターン用文字列

      int idx = bfMatch(s1, s2);   // 文字列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);
      }
   }
}

戻る