8-1 力まかせ法
順探索
- ちょっと焦げ臭い。もっとスマートに書けそうだが・・・
- 進捗表示が意外とめんどかった。
- 探索対象文字列の何文字目から探索しているかを表示する部分で、フラグ処理が必要なんだが、ここをうまくかければ、綺麗になりそう。
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)
- int lastIndexOf(String str)
- int lastIndexOf(String str, int fromIndex)