기억하고싶은것들

문자열 탐색 알고리즘

Rabin-Karp는 Hashing을 이용하여 문자열에서 특정 패턴과 일치하는지 찾는 알고리즘이다.

문자열에서 찾고자 하는 패턴의 길이만큼 hash값으로 변환하여, 패턴과 hash값이 같은지 확인을 하며

일치하지 않는 다면 한 칸씩 뒤로 이동하며 비교를 반복한다.

다만, hash값이 같다고 무조건 같은 패턴일 수는 없다.

그렇기 때문에 hash값이 같은 경우에는 문자열에 값과 패턴의 값을 일대일 매칭 하며 비교하는 과정도 필요하다.

기본적인 아이디어는 간단하다. 다만, 문자열을 이동하며 hash값을 계산해야 하는데 이 또한 효율적으로 찾을 수 있다. 

Rolling Hash

sliding window와 같이 문자열을 훑으면서 hash 값을 구하는데 유용하다.

주어진 문자열을 처음부터 끝까지 패턴과 비교하면서 해시값을 구하는데, 중복되는 부분의 해시값은 그대로 두고 업데이트되는 부분만 해시값을 계산해주어서 중복되는 연산을 줄일 수 있다.

위의 그림같은 경우에는 abec의 hash값 dece의 hash값을 구한다고 해보자

두 문자의 공통 부분인 dec는 그대로 두고 변경된 부분만 적용하면 된다.

우선 adec의 hash값은 

97*2^3 + 100*2^2 + 101*2^1 + 99*2^0 = 1477

다음으로 dece의 hash값은 아래와 같이 계산할 수 있다.

(1477 - 97*2^3) * 2 + 101*2^0 = 1503

adec문자에서 a는 제외되었기 때문에 a에 해당하는 값을 빼고 

한 자리씩 앞으로 이동했기 때문에 곱하기 2를 해주고 

마지막에 추가된 문자를 더해주면 된다.

    public List<Integer> find(String parent, String pattern) {

        int parentHash = 0, patternHash = 0, power = 1;

        int parentLen = parent.length();
        int patternLen = pattern.length();

        List<Integer> idxList = new ArrayList<>();

        for (int i = 0; i < parentLen - patternLen; i++) {

            if (i == 0) {
                for (int j = 0; j < patternLen; j++) {
                    parentHash = parentHash + parent.charAt(patternLen - 1 - j) * power;
                    patternHash = patternHash + pattern.charAt(patternLen - 1 - j) * power;

                    if (j < patternLen - 1) {
                        power *= 2;
                    }
                }
            } else {
                parentHash = (parentHash - parent.charAt(i - 1) * power) * 2 
                    + parent.charAt(i + patternLen - 1);
            }

            if (parentHash == patternHash) {
                boolean found = true;

                for (int j = 0; j < patternLen; j++) {
                    if (parent.charAt(i + j) != pattern.charAt(j)) {
                        found = false;
                        break;
                    }
                }

                if (found) {
                    idxList.add(i + 1);
                }
            }
        }

        return idxList;
    }