いももちのきもち

新米プログラマによる技術的メモ

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)]);
        }
    }
}

残念ながら、今回は大きいデータサイズのテストケースを制限時間内に通過できませんでした。
次は他の解答者を参考にしつつ、別のアルゴリズムを用いて解いてみます。