[알고리즘 문제 해결 전략] 20장 문자열

짚더미에서 바늘찾기

  주어진 긴 '짚더미(haystack)' 문자열 H가 '바늘(needle)' 문자열 N을 부분 문자열로 포함하는지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제를 문자열 검색 문제라고 한다. 예를 들어 H="avava"는 N="ava"를 두 번 포함하며, 각각의 시작 위치는 0,2이다.

import java.util.ArrayList;
import java.util.List;

public class NaiveSearch {
	// '짚더미'H의 부분 문자열로 '바늘'N이 출현하는 시작 위치들을 모두 반환한다.
    public static List<Integer> naiveSearch(String H, String N) {
        List<Integer> ret = new ArrayList<>();
        // 모든 시작 위치를 다 시도해본다.
        for (int begin = 0; begin + N.length() <= H.length(); ++begin) {
            boolean matched = true;
            for (int i = 0; i < N.length(); ++i) {
                if (H.charAt(begin + i) != N.charAt(i)) {
                    matched = false;
                    break;
                }
            }
            if (matched) {
                ret.add(begin);
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        String H = "Hello, World! Hello, Hello!";
        String N = "Hello";
        List<Integer> indices = naiveSearch(H, N);
        System.out.println("Indices where \"" + N + "\" is found in \"" + H + "\": " + indices);
        // result -> Indices where "Hello" is found in "Hello, World! Hello, Hello!": [0, 14, 21]
    }
}

  이 코드는 단순한 문자열 검색 알고리즘을 구현한 결과이다. 이 코드는 구현은 단순하지만 비효율적이라는 단점이 있다. 예를 들어 H와 N이 모두 a로만 구성된 긴 문자열이라고 해보자. 이 알고리즘은 일단 |H|-|N|+1개의 모든 시작 위치에 대해서 비교를 수행한다. 시작 위치의 수는 O(|H|) 라고 할 수 있다. 또한 각각 비교에 걸리는 시간은 O(|N|)이 되므로 총 시간 복작도는 O(|H|*|N|)이 된다. 

 

KMP 알고리즘

색깔로 글자를 구분하면 더 잘 이해할 꺼 같아서 바꿔봤다. 일치?를 보면 no 부분은 볼 것도 없이 ok로 점프하면 더 효율적으로 검색을 할 수 있다. 일치한 글자의 수는 항상 0~|N| 사이의 정수이기 때문에, 전처리 과정에서 이 정보들을 미리 계산해 저장해 둘 수 있다. 이와 같은 최적화를 적용한 문자열 검색 알고리즘을 KMP 알고리즘이라고 부른다. 

 

다음 시작 위치 찾기

"aabaaba"의 접두사도 되고 접미사도 되는 문자열이 "aaba"와 "a"의 두가지가 있지만, "aaba"를 이용해 시작 위치를 3만큼 옮겼다.(a를 찾는 건 너무 쉽다) 

pi[i]=N[...i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이

 

실제 문자열 검색의 구현

시작 위치를 움직인 이후 첫 글자부터 다시 대응시켜 나갈 필요가 없다. 새로운 위치에서 비교를 시작하더라도 matched를 pi[matched-1]으로 변경하고 비교를 계속하면 된다.

package Book20장;
import java.util.ArrayList;
import java.util.List;

public class KMPSearch {
    public static void main(String[] args) {
        String haystack = "abcabcababab";
        String needle = "abab";
        List<Integer> positions = kmpSearch(haystack, needle);

        if (positions.isEmpty()) {
            System.out.println("Needle not found in haystack");
        } else {
            System.out.println("Needle found at positions: " + positions);
        }
    }
    
    public static List<Integer> kmpSearch(String H, String N) {
       //H 글자 안에 존재하는 N의 시작 위치를 반환
        int n = H.length();
        int m = N.length();
        List<Integer> ret = new ArrayList<>();
        //pi[i] = N[..i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이
        
        int[] pi = getPartialMatch(N);
        //begin, matched 0 부터 시작
        int begin = 0;
        int matched = 0;

        while (begin <= n - m) {
           //만약 H의 (begin + matched) 순서의 단어와 N의 matched의 단어가 같다면
            if (matched < m && H.charAt(begin + matched) == N.charAt(matched)) {
                matched++;
                //모든 글자가 모두 일치했다면 답에 추가
                if (matched == m) {
                    ret.add(begin);
                }
            } else {
               // 예외 : matched가 0 인 경우엔 다음 칸에서 계속
                if (matched == 0) {
                    begin++;
                } else {
                    begin += matched - pi[matched - 1];
                    //begin을 옮겼다고 처음부터 다시 비교할 필요가 없다
                    //옮긴 후에도 pi[matched-1] 만큼은 항상 일치하기 떄문
                    matched = pi[matched - 1];
                }
            }
        }

        return ret;
    }

    private static int[] getPartialMatch(String N) {
        int m = N.length();
        int[] pi = new int[m];//pi[i] = N[..i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이
        int begin = 1; // begin=0은 자기자신이므로 제외
        int matched = 0; // 현재까지 일치한 글자 수

        // 비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록한다.
        while (begin + matched < m) {
            if (N.charAt(begin + matched) == N.charAt(matched)) {
                matched++;// 일치한 글자 수 증가
                pi[begin + matched - 1] = matched;
            } else {
                if (matched == 0) { // match 된 것이 없으면 begin을 한칸 옮기기
                    begin++;
                } else {
                    begin += matched - pi[matched - 1]; // 일치한 글자가 있는 경우, begin 이동
                    matched = pi[matched - 1];// 일치한 글자 수 갱신
                }
            }
        }

        return pi;
    }

}