[Java] 문자열 탐색(브루트 포스, KMP, 보이어 무어)

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 을 개인적으로 정리하는 글임을 알립니다.

---

문자열 탐색

문자열 탐색이란 어떤 문자열 안에 특정 문자열이 들어 있는지를 조사하고, 들어있다면 그 위치를 찾는 것을 말한다.

이 글에서는 검색할 문자열을 패턴이라 하고 문자열 원본을 텍스트라고 하겠다.

문자열 탐색 알고리즘에는 아래와 같은 방법이 있다.

• 브루트 포스
• KMP
• 보이어-무어

 

브루트 포스

브루트 포스(Brute Force)는 가장 간단하고 직접적인 문자열 탐색 방법 중 하나이다.

이 방법은 텍스트에서 패턴을 한 글자씩 비교하면서 탐색하는 단순한 방법이다.

각 가능한 위치에서 비교를 수행하고, 일치하지 않으면 다음 위치로 이동하여 계속 비교를 수행한다.

브루트 포스 문자열 탐색 알고리즘의 주요 특징은 다음과 같다

1. 비교적 간단한 구현: 브루트 포스는 간단하게 구현할 수 있는 장점이 있다.
   각 위치에서 패턴의 길이만큼의 문자를 비교하면서 이동한다.
2. 모든 가능한 위치에서 비교: 브루트 포스는 텍스트와 패턴을 모든 가능한 위치에서 비교하기 때문에, 패턴이 텍스트에서 나타날 수 있는 모든 위치를 찾을 수 있다.
3. 시간 복잡도: 최악의 경우 시간 복잡도는 O(n * m)이며, 여기서 n은 텍스트의 길이, m은 패턴의 길이이다.

브루트 포스는 간단하고 직관적이지만, 텍스트와 패턴의 길이가 큰 경우에는 비효율적일 수 있다.

따라서 브루트 포스는 간단한 문제나 작은 데이터셋에서 사용될 수 있으며, 더 효율적인 문자열 탐색 알고리즘들이 선호되는 경우도 있다.

public class Main
{
    public static int bruteForceSearch(String text, String pattern)
    {
        for (int i = 0; i <= text.length() - pattern.length(); i++)
        {
            int j;
            for (j = 0; j < pattern.length(); j++)
            {
                if (text.charAt(i + j) != pattern.charAt(j)) break;
            }
            if (j == pattern.length())  return i; // 패턴이 발견된 위치 반환
        }
        return -1; // 패턴이 발견되지 않음
    }

    public static void main(String[] args)
    {
        String text = "Hello, World!";
        String pattern = "World";

        int result = bruteForceSearch(text, pattern);

        if (result != -1) System.out.println("패턴이 발견된 위치: " + result);
        else System.out.println("패턴이 발견되지 않음");
    }
}

 

String.indexOf(), String.lastIndexOf() 와 String.contain()
Java에서 문자열 내에서 특정 문자열 또는 문자의 인덱스를 찾는 데 사용되는 메서드이다.

1. String.indexOf(String str) 메서드
- 주어진 문자열이 처음으로 등장하는 위치의 인덱스를 반환한다.
- 만약 주어진 문자열이 포함되어 있지 않다면 -1을 반환한다.

public class IndexOfExample {
    public static void main(String[] args) {
        String text = "Hello, World! Hello";
        String pattern = "World";

        int firstIndex = text.indexOf(pattern);
        System.out.println("처음으로 발견된 위치: " + firstIndex);

        // 두 번째로 발견된 위치를 찾기
        int secondIndex = text.indexOf(pattern, firstIndex + 1);
        System.out.println("두 번째로 발견된 위치: " + secondIndex);
    }
}​

2. String.lastIndexOf(String str) 메서드
- 주어진 문자열이 마지막으로 등장하는 위치의 인덱스를 반환한다.
- 만약 주어진 문자열이 포함되어 있지 않다면 -1을 반환한다.

public class LastIndexOfExample {
    public static void main(String[] args) {
        String text = "Hello, World! Hello";
        String pattern = "Hello";

        int lastIndex = text.lastIndexOf(pattern);
        System.out.println("마지막으로 발견된 위치: " + lastIndex);

        // 두 번째로 마지막으로 발견된 위치를 찾기
        int secondLastIndex = text.lastIndexOf(pattern, lastIndex - 1);
        System.out.println("두 번째로 마지막으로 발견된 위치: " + secondLastIndex);
    }
}

3. String.contain(String str) 메서드
- 이 메서드는 특정 문자열이 다른 문자열에 포함되어 있는지 여부를 확인한다.
- contains 메서드는 boolean 값을 반환하며, 포함되어 있다면 true, 그렇지 않으면 false를 반환한다.

public class ContainsExample {
    public static void main(String[] args) {
        String text = "Hello, World!";

        // "World" 문자열이 포함되어 있는지 확인
        boolean containsWorld = text.contains("World");
        System.out.println("Contains 'World': " + containsWorld);

        // "Java" 문자열이 포함되어 있는지 확인
        boolean containsJava = text.contains("Java");
        System.out.println("Contains 'Java': " + containsJava);
    }
}

 

 

KMP

브루트 포스 방법은 일치하지 않는 문자를 만난 단계에서 그때까지 검사한 결과를 버리고 패턴을 텍스트의 다음 칸으로 옮긴 다음 패턴의 첫 번째 문자부터 다시 검사한다.

하지만 KMP 알고리즘은 검사한 결과를 버리지 않고 이를 효과적으로 활용하는 알고리즘이다.

이 알고리즘의 시간 복잡도는 O(n)이다.

주로 파일에서 순서대로 읽어들이면서 검색하는 경우 사용한다.

반면 처리가 복잡하다는 점과 패턴 안에 반복하는 요소가 없으면 효율이 떨어진다는 단점이 있다.

좀 더 자세한 설명은 아래의 포스트를 참고해주세요

2023.11.28 - [자료구조 & 알고리즘/알고리즘] - [Java]KMP 문자열 탐색 알고리즘

[Java]KMP 문자열 탐색 알고리즘

 

아래의 그림과 같이 텍스트, 패턴의 1번째 문자부터 순서대로 검사를 한다.

텍스트 1번째 문자 Z는 패턴에 없으므로 바로 일치하지 않는다고 판단한다.

 

이제 패턴을 1킨 뒤로 옮긴다. 이때 패턴의 처음부터 순서대로 검사하면 패턴의 마지막 문자 D가 텍스트의 X와 일치하지 않는다.

여기서 텍스트의 주황색 문자 AB와 패턴의 AB가 일치하고 있는 것에 주목해야한다.

이 부분을 이미 검사를 마친 부분으로 보면, 텍스트의 X 다음 문자부터 패턴의 CABD가 일치하는지만 검사하면 된다.

 

그래서 패턴을 아래와 같이 AB가 겹치도록 한 번에(3칸) 이동시키고 3번째 문자인 C부터 검사하면 된다.

 

이와 같이 KMP 알고리즘은 텍스트와 패턴 사이에 겹치는 부분을 찾아내 검사를 다시 시작할 위치를 구하여 패턴을 한번에 많이 옮기는 알고리즘이다.

하지만 패턴을 옮길 때마다 몇 번째 문자부터 다시 검색을 시작할지 계산해야 한다면 높은 효율을 기대할 수 없다.

그래서 몇 번째 문자부터 다시 검색할지에 대한 값을 미리 표로 만들어 이 문제를 해결한다.

 

표를 작성하려면 패턴 안에서 중복되는 문자열을 찾아야 한다.

패턴 안에서 중복되는 문자열을 찾기 위해 패턴끼리 겹쳐 놓고 생각해보자.

텍스트와 패턴의 1번째 문자가 서로 다른 경우 패턴을 1칸 뒤로 옮기고 패턴의 1번째 문자부터 다시 검사해야 하는 것은 분명하므로 패턴의 2번째 문자부터 생각한다.

패턴 "ABCABD"를 두 줄로 겹쳐 놓고 아랫줄을 1칸 뒤로 옮긴다.

아래의 그림을 보면 주황색 부분이 겹치지 않으므로 패턴을 다시 1칸 옮길 경우 1번째 문자부터 검사를 다시 시작해야 함을 알 수 있다.

그러므로 2번째 문자(B)의 다시 시작하는 값은 0이다.

이는 패턴의 1번째 문자(인덱스 0)부터 검사를 다시 시작한다는 의미이다.

다시 패턴을 1칸 뒤로 옮긴다.

문자가 일치하지 않으므로 표에서 3번째 문자(C)의 값을 0으로 한다.

다시 패턴을 1칸 뒤로 옮기면 "AB"가 일치한다.

여기서 아래와 같은 사실을 알 수 있다.

따라서 표에서 4번째와 5번째 문자의 경우 다시 시작하는 값을 1, 2로 한다.

 

이어서 패턴을 2칸 뒤로 옮기면 문자가 일치하지 않는다.

표에서 패턴의 마지막문자 'D'의 값을 0으로 한다.

이제 표 만들기가 끝이 났다.

public class Main
{
    public static int[] makeTable(String pattern)
    {
        int[] failure = new int[pattern.length()];

        int j = 0;
        for (int i = 1; i < pattern.length(); i++)
        {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) j = failure[j - 1];
            if (pattern.charAt(i) == pattern.charAt(j))
            {
                failure[i] = j + 1;
                j++;
            }
        }
        return failure;
    }

    public static int kmpSearch(String text, String pattern)
    {
        int[] failure = makeTable(pattern);

        int i = 0, j = 0;
        while (i < text.length())
        {
            if (text.charAt(i) == pattern.charAt(j))
            {
                if (j == pattern.length() - 1) return i - j;  // 패턴이 발견된 위치 반환
                i++;
                j++;
            }
            else if (j > 0)  j = failure[j - 1];
            else i++;
        }

        return -1;  // 패턴이 발견되지 않음
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "CD";

        int result = kmpSearch(text, pattern);

        if (result != -1) System.out.println("패턴이 발견된 위치: " + result);
        else System.out.println("패턴이 발견되지 않음");
    }
}

 

보이어 무어

보이어 무어 알고리즘은 KMP 알고리즘보다 이론과 실제 모두 더 우수한 알고리즘이다.

이 알고리즘은 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정한다.

아래의 그림처럼 비교 범위의 텍스트에 패턴이 없는 문자가 있다면 그 위치까지 건너뛸 수 있다.

 

그러므로 a~d까지의 비교를 생략하고 패턴을 단숨에 4칸 뒤로 옮겨 아래와 같은 위치까지 건너 뛸 수 있다.

 

패턴의 A는 텍스트의 Z와 다르다.

그리고 Z는 패턴에 없는 문자이다. 따라서 패턴을 한꺼번에 3칸 옮겨도 된다.

 

패턴의 길이를 n이라 하면, 텍스트에서 패턴에 들어 있지 않은 문자를 만날 경우 패턴 자체를 n만큼 옮기는 것이 아니다.

 (인덱스 4에서 n만큼 옮기는 것이 아니라는 뜻)

현재 검사하고 있는 텍스트 안의 문자 위치(인덱스 6)로부터 패턴이 n만큼 멀어지도록 패턴을 옮기는 것이다.

패턴의 길이는 4이므로 인덱스 6에서 4를 더한 10에서 다시 비교를 시작한다.

이때 문자 A는 패턴의 1, 3번째 인덱스에 들어있다.

이런 경우 [b]와 같이 패턴의 뒤쪽에 위치한 A가 텍스트와 겹치도록 패턴을 1칸만 옮긴다. ( 4 - 2 - 1  = 1)

이때 [d]처럼 패턴의 앞쪽에 위치한 A와 겹치도록 3칸을 옮기면 안된다.

[b]와 같이 한 칸만 옮기면 아래와 같은 결과가 나타난다.

보이어 무어 알고리즘에서도 각각의 문자를 만났을 때 패턴을 옮길 크기를 알려주는 표를 미리 만들어 두어야 한다.

패턴 문자열의 길이가 n일 때 옮긴 크기는 아래와 같은 방법으로 결정된다.

 

패턴에 들어 있지 않은 문자를 만난 경우

1. 패턴을 옮길 크기는 n이다. 따라서 비교하고 있는 텍스트의 인덱스로부터 n만큼 이동한다.

 

패턴에 들어 있는 문자를 만난 경우

1. 해당 문자의 마지막 인덱스가 k이면 패턴을 옮길 크기는 n - k - 1이다.
   해당 문자가 패턴의 두 곳에 들어있으면 마지막 인덱스를 선택하여 패턴을 옮긴다.
2. 패턴의 마지막 문자가 패턴 안에 중복해서 들어 있지 않은 경우(예를 들어 ABAC의 C는 패턴 안에 1개만 있다)
   패턴의 옮길 크기를 n으로 한다. 텍스트에서 이런 문자를 만날 경우 이동하지 않고 바로 앞 문자를 비교한다.

 

위와 같은 설명은 다른 관점에서 보이어 무어 알고리즘을 설명하는 느낌을 받았다.

일반적인 설명은 아래의 포스팅을 참고하면 좋을 것 같다.

2023.11.29 - [자료구조 & 알고리즘/알고리즘] - [알고리즘]보이어-무어(Boyer-Moore) 문자열 탐색 알고리즘

[알고리즘]보이어-무어(Boyer-Moore) 문자열 탐색 알고리즘

public class Main
{
    static int bmMatch(String txt, String pat)
    {
        int pt;                           // txt를 따라가는 커서
        int pp;                           // pat를 따라가는 커서
        int txtLen = txt.length();        // txt의 문자 개수
        int patLen = pat.length();        // pat의 문자 개수
        int[] skip = new int[Character.MAX_VALUE + 1];    // 건너뛰기 표(skip 테이블)

        // skip 테이블 작성
        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;  // pt == patLen - 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.charAt(pt)] > patLen - pp) ? skip[txt.charAt(pt)] : patLen - pp;
        }
        return -1;                             // 검색 실패
    }

    public static void main(String[] args) {

        String s1 = "ABASDASD";                   // 텍스트용 문자열
        String s2 = "ASD";                    // 패턴용 문자열

        int idx = bmMatch(s1, s2);                    // 문자열 s1에서 문자열 s2를 BM법으로 검색

        if (idx == -1) System.out.println(-1);
        else  System.out.println(idx);
    }
}