[leetcode] 28. Implement strStr()

문제

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

 

풀이

문자열 내에 특정 문자열이 있는지 찾는 알고리즘으로 kmp 알고리즘이 유명하다.

이를 이용한다. 

Time Complexity : $O(n+m)$

 

코드

class Solution {
public:
    int strStr(string haystack, string needle) {
        int hl = haystack.length();
        int nl = needle.length();
        if(nl==0) return 0;
        
        vector<int> fail;
        fail.resize(nl,0);
        int j=0;
        for(int i = 1; i< nl ; i++)
        {
            while(j > 0 && needle[i] != needle[j]) j = fail[j-1];
            if(needle[i] == needle[j]) fail[i] = ++j;
        }
        j=0;
        for(int i=0;i<hl;i++)
        {
            while(j>0 && haystack[i] != needle[j]) j = fail[j-1];
            if(haystack[i] == needle[j])
            {
                if(j==nl-1) return i-nl+1;
                else j++;
            }
        }
        
        return -1;
    }
};