문자열 검색

---

• 문자열 검색이란 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어있다면 그 위치를 찾아내는 것을 말한다.
• "STRING"에서 "IN"을 검색하면 3(인덱스)을 반환한다.

브루트-포스법

---

• 순서대로 하나하나씩 비교하는 방법이다.

코드

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

---

• java.lang.String 클래스는 문자열을 검색하는 indexOf 메서드와 lastIndexOf 메서드를 제공한다.

1. int indexOf(String str)
2. int indexOf(String str, int fromIndex)
3. int lastIndexOf(String str) : str을 배열의 뒤부터 찾는다.
4. int lastIndexOf(String str, int fromIndex)

KMP법

---

• 브루트-포스법은 다른 문자를 만나면 패턴에서 문자를 검사했던 위치 결과를 버리고 다음 텍스트의 위치로 1칸 이동한 다음 다시 패턴의 첫번째 문자부터 검사한다.
• 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법

---

• KMP법보다 효율이 더 우수하기 때문에 많이 사용한다.
• 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정한다.
• 다음의 규칙을 따라 A~Z까지 표를 만들 수 있다.
  1. 패턴에 들어있지 않은 문자를 만난 경우 : 패턴을 옮길 크기는 n이다.
  2. 패턴에 들어있는 문자를 만난 경우
     • 마지막에 나오는 위치의 인덱스가 k이면 패턴을 옮길 크기는 n - k - 1이다.
     • 같은 문자가 패턴 안에 중복해서 들어있지 않다면, 패턴을 옮길 크기는 n이다.

코드

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; // 검색 실패
}