문제

답안 1

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

답안 2

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() > haystack.length()) {
            return -1;
        }

        if (needle.length() == haystack.length()) {
            if (!needle.equals(haystack)) {
                return -1;
            }
        }

        int needleHash = 0, haystackHash = 0, power = 1;
        for (int i = 0; i < needle.length(); i++) {
            needleHash = 2 * needleHash + needle.charAt(i);
            haystackHash = 2 * haystackHash + haystack.charAt(i);
            if (i < needle.length() - 1) {
                power *= 2;
            }
        }

        if (needleHash == haystackHash) {
            return 0;
        }

        for (int i = 1; i <= haystack.length() - needle.length(); i++) {
            haystackHash = 2 * (haystackHash - haystack.charAt(i - 1) * power)
                    + haystack.charAt(i + needle.length() - 1);

            if (haystackHash == needleHash) {
                return i; 
            }
        }

        return -1;
    }
}

이것은 Rabin-Karp 알고리즘을 사용한 코드이다.

각 substring의 해쉬값을 구하며 비교하는 알고리즘인데, 최적화는 처음 해쉬를 구할때만 substring.length()만큼의 time complexity가 필요하고, 다음 문자를 구할때에는 이전 해쉬값에서 가장 처음 문자의 value값을 빼고, 2를 곱한다음, 가장 마지막(가장 최근)에 추가 될 문자의 해쉬값을 더해주면 된다는 점에서 O(1)으로 비교할 수 있다는 점에있다.