BohYoh.comトップページへ

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

戻る  

演習8-3の解答

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

// 演習8-3 // KMP法による文字列探索(照合過程の詳細を表示) import java.util.Scanner; class KMPmatchEx {    //--- KMP法による文字列探索 ---//    static int kmpMatch(String txt, String pat) {       int pt = 1;                                 // txtをなぞるカーソル       int pp = 0;                                 // patをなぞるカーソル       int count = 0;                              // 比較回数       int[] skip = new int[pat.length() 1];   // スキップテーブル       int k = -1;       // スキップテーブルの作成       System.out.println("スキップ表作成");       skip[pt0;       while (pt != 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 * 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++;          if (pat.charAt(pt== pat.charAt(pp))             skip[++pt= ++pp;          else if (pp == 0)             skip[++pt= pp;          else             pp = skip[pp];       }       // 探索       System.out.println("探索");       pt = pp = 0;       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 * 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++;          if (txt.charAt(pt== pat.charAt(pp)) {             pt++;             pp++;          else if (pp == 0)             pt++;          else             pp = skip[pp];       }       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 = kmpMatch(s1, s2);   // 文字列s1から文字列s2をKMP法で探索       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);       }    } }


戻る