[LeetCode][Kotlin] 28. Find the Index of the First Occurrence in a String

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

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

needle과 haystack이라는 두 문자열이 주어지면 haystack에서 needle이 처음 나타나는 인덱스를 반환하거나, needle이 haystack의 일부가 아닌 경우 -1을 반환합니다.

 

Example 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.

 

Example 2:

Input: haystack = "leetcode", needle = "leeto"

Output: -1

Explanation: "leeto" did not occur in "leetcode", so we return -1.

 

Constraints:

• 1 <= haystack.length, needle.length <= 10^4
• haystack and needle consist of only lowercase English characters.

---

코드 1

class Solution {
    fun strStr(haystack: String, needle: String): Int {
        return haystack.indexOf(needle)
    }
}

 

코드 2 (KMP: Knuth-Morris-Pratt)

• 기존 알고리즘(이중 for문)에서는 needle 을 찾을 때 다른 문자가 나왔을 경우, 다시 돌아가서 검사할때 중복되는 경우가 존재한다.

• needle(바늘)과 haystack(건초 더미) : haystack = "ababcabcabababd", needle = "ababd"
• needle 에 대한 LPS(Longest Prefix Suffix) 를 만든다. [0, 0, 1, 2, 0]

• haystack 과 needle 을 비교할 때, 문자가 일치하지 않을 경우 처음으로 돌아가는 것이 아니라 LPS 배열을 활용하여 비교를 계속 진행한다.

class Solution {
    fun strStr(haystack: String, needle: String): Int {
        // if (needle.isEmpty()) return 0
        val lps = IntArray(needle.length)

        var prevLPS = 0
        var i = 1
        while (i < needle.length) {
            if (needle[i] == needle[prevLPS]) {
                lps[i] = prevLPS + 1
                prevLPS++
                i++
            } else if (prevLPS == 0) {
                lps[i] = 0
                i++
            } else {
                prevLPS = lps[prevLPS - 1]
            }
        }

        i = 0
        var j = 0
        while (i < haystack.length) {
            if (haystack[i] == needle[j]) {
                i++
                j++
            } else if (j == 0) {
                i++
            } else {
                j = lps[j - 1]
            }

            if (j == needle.length) {
                return i - needle.length
            }
        }

        return -1
    }
}