Leetcode - 28. Find the Index of the First Occurrence in a String

문제

주어진 haystack 문자열에서 needle 문자열을 탐색했을때, 발견된 첫번째 인덱스를 리턴, 없다면 -1리턴.

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

해결 아이디어

• 1. 해시값 비교하기. O(n*m)
• 2. 해시값 비교 + 슬라이딩 윈도우 O(n + m)
• 3. kmp 알고리즘

풀이 1 - O(n*m)

class Solution {
public:
    int strStr(string haystack, string needle) {
        std::hash<string> str_hash;
        size_t hval_needle = str_hash(needle);
        int nsize = needle.length();
        // abcd (cd)
        
        for (int i = 0; i + nsize - 1 < haystack.length(); i++) {
            if (str_hash(haystack.substr(i, nsize)) == hval_needle)
                return i;
        }
        return -1;
    }
};

풀이 2 - O(n+m)

해시값 비교 + 슬라이딩 윈도우를 적용.
haystack문자열을 순회하면서 needle길이 m 만큼 순회하여 해시값을 계속 만들(n*m) 필요없이.
해시값을 sliding window 기법으로 맨앞과 그다음값을 빼고 더하는 방식으로 O(n)만에 계산.
해시 계산을 단순하게 각 문자열 아스키값을 더했기 때문에, 만약 해시값이 같은경우, double check하는 O(m)짜리 추가 루틴 수행 필요함.

결과는 100%가 나왔음.Runtime: 0 ms, faster than 100.00% of C++ online submissions

class Solution {
public:
    unsigned int make_hash(string s, int st, int end) {
        unsigned int sum = 0;
        for (int i = st; i < end; i++) {
            sum += (unsigned int)s[i];
        }
        return sum;
    }
    bool double_check(string s1, string s2, int st, int end) {
        int idx = 0;
        for (int i = st; i < end; i++) {
            if (s1[i] != s2[idx++])
                return false;
        }
        return true;
    }
    int strStr(string haystack, string needle) {
        int nsize = needle.size();
        unsigned int hval_needle = make_hash(needle, 0, nsize);
        unsigned int hval_window = make_hash(haystack, 0, nsize);
        //cout << hval_needle << endl;
        
        if (hval_window == hval_needle && double_check(haystack, needle, 0, nsize))
            return 0;
        for (int i = 1; i + nsize <= haystack.length(); i++) {
            hval_window -= (unsigned int)haystack[i - 1];
            hval_window += (unsigned int)haystack[i + nsize - 1];
            //cout << hval_window << " "; 
            if (hval_window == hval_needle && double_check(haystack, needle, i, i + nsize))
                return i;
        }
        return -1;
    }
};