BMアルゴリズムを用いて部分文字列を検索する
最近AOJ(Aizu Online Judge)の「Algorithms and Data Structures I」に「String Search」の練習問題が追加されたので解いてみることにしました。
部分文字列の検索は、生物学分野でも膨大なDNA情報から特定配列を抽出する問題など、親しみがわく分野ですね。
アルゴリズムは以下の記事を参考に、BM法を採用しました。
文字列検索(BM法)
String Search | Aizu Online Judge
入力1行目にtext, 2行目にpatternが与えられます。text中にpatternがある場合、patternの左端の位置を都度出力します。
ProgrammingContests/ALDS1_14_B.java at master · toricor/ProgrammingContests · GitHub
import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String text = br.readLine(); String pattern = br.readLine(); bmSearch(text, pattern); } public static void bmSearch(String text, String pattern){ int textLen = text.length(); int patnLen = pattern.length(); int[] skip = new int[128]; //store ascii code chars for (int i = 0; i < 128; i++){ skip[i] = patnLen; } for (int i = 0; i < patnLen - 1; i++){ skip[pattern.charAt(i)] = patnLen - i - 1; } int i = patnLen - 1; //iはtext中で着目している位置 while (i < textLen){ int j = patnLen - 1; //jはpattern中で着目している位置 while (text.charAt(i) == pattern.charAt(j)){ if (j == 0){ System.out.println(i); break; } i--; j--; } i += Math.max(patnLen - j, skip[text.charAt(i)]); } } }
残念ながら、今回は大きいデータサイズのテストケースを制限時間内に通過できませんでした。
次は他の解答者を参考にしつつ、別のアルゴリズムを用いて解いてみます。