検索文字列

ブルートペルシャ法

コード#コード#

static int bfMath(String txt, String pat) {
  int pt = 0; // txt 커서
  int pp = 0; // pat 커서(찾는 문자열)
  
  while (pt != txt.length() && pp != pat.length()) {
    if (txt.charAt(pt) == pat.charAt(pp)) {
      pt++;
      pp++;
    } else {
      pt = pt - pp + 1;
      pp = 0;
    }
  }
  if (pp == pat.length())
    return pt - pp;
  return -1;
}

String.indexOf

KMPメソッド

KMP法は検査位置結果を捨てない効率的なアルゴリズムである.

コード#コード#

static int kmpMatch(String txt, String pat) {
  int pt = 1;
  int pp = 0;
  int[] skip = new int[pat.length() + 1]; // 건너뛰기 표
  
  skip[pt] = 0;
  while (pt != pat.length()) {
    if (pat.charAt(pt) == pat.charAt(pp))
      skip[++pt] = ++pp;
    else if (pp == 0)
      skip[++pt] = pp;
    else
     pp = skip[pp];
  }
}

Boyer-Moore法

コード#コード#

static int bmMatch(string txt, String pat) {
  int pt;
  int pp;
  int txtLen = txt.length();
  int patLen = pat.length();
  int[] skip = new int[Character.MAX_VALUE + 1]; // 건너뛰기 표
  
  // 건너뛰기 표 만들기
  for (pt = 0; pt <= Character.MAX_VALUE; pt++)
    skip[pt] = patLen;
  for (pt = 0; pt < patLen - 1; pt++)
    skip[pat.charAt(pt)] = patLen - pt - 1;
    
  // 검색
  while (pt < txtLen) {
    pp = patLen - 1; // pat의 끝 문자에 주목
    
    while (txt.charAt(pt) == pat.charAt(pp)) {
      if (pp == 0)
        return pt; // 검색 성공
      pp--;
      pt--;
    }
    pt += (skip[txt.chatAt(pt)] > patLen - pp) ? skip[txt.charAt(pt)] : patLen - pp;
  }
  return -1; // 검색 실패
}