[LeetCode - C] 28. Implement strStr()

Implement strStr() - LeetCode

Implement strStr().

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

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

 

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Example 3:

Input: haystack = "", needle = ""
Output: 0

 

Constraints:

• 0 <= haystack.length, needle.length <= 5 * 104
• haystack and needle consist of only lower-case English characters.

---

Solution 1

 

처음에는 i, j 이용해 haystack[i]마다

 

처음부터 끝까지 needle 검사했다.

 

결과는 잘 나오지만 time limit에 걸려 통과가 안 돼서

 

실패 함수 이용하여 kmp알고리즘으로 해결했다.

 

[알고리즘] 실패함수(문자열 검색 - KMP 알고리즘 관련)

int strStr(char * haystack, char * needle)
{
    if (!*needle)
        return (0);
    if (!*haystack)
        return (-1);
    int failfunc[strlen(needle)];
    int i;
    int j;
    
    i = 0;
    j = 1;
    failfunc[0] = 0;
    while  (needle[j])
    {
        while (i > 0 && needle[i] != needle[j])
            i = failfunc[i - 1];
        if (needle[i] == needle[j])
            failfunc[j] = ++i;
        else
            failfunc[j] = 0;
        j++;
    }
    i = 0;
    j = 0;
    while (haystack[i])
    {
        while (j > 0 && haystack[i] != needle[j])
            j = failfunc[j - 1];
        if (haystack[i] && needle[j] && haystack[i] == needle[j])
            j++;
        if(!needle[j])
            return (i - j + 1);
        i++;
    }
    return (-1);
}

---

총평

 

전에 실패함수를 한 번 정리 했음에도 어떻게 하는건지

 

생각나지 않아서 한참 보고 나서 실패 함수 이용하여

 

혼자서 해결하려했는데 아이디어가 잘 떠오르지 않아 

 

kmp알고리즘 참고해서 풀었다.