문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

두 문자열 needle과 haystack이 주어졌을때, haystack에 needle의 처음 발견된 인덱스를 또는, haystack에 needle이 없다면 -1을 반환해라.

Example

#1
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad"는 인덱스 0과 6에서 발견된다.

#2
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto"는 "leetcode"에서 발견되지 않았다. 그래서 -1을 반환한다.

Constraints

• 1 <= haystack.length, needle.length <= 10^4
• haystack와 needle은 오직 영문 소문자로만 존재한다.

Solved

needle이 처음으로 haystack에서 나타나는 인덱스를 반환하면 되는 문제이다. 쉽게 해결하기 위해서 indexOf를 사용하면 된다.

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

그리고 haystack와 needle 두 문자열을 순회하면서 비교할 수도 있다.

class Solution {
    public int strStr(String haystack, String needle) {
        int[] lps = new int[needle.length()];
        int idx = 0;

        for (int i = 1; i < needle.length(); i++) {
            while (!(idx == 0 || needle.charAt(i) == needle.charAt(idx))) {
                idx = lps[idx - 1];
            }
            
            if (needle.charAt(i) == needle.charAt(idx)) {
                idx += 1;
                lps[i] = idx;
            }
        }

        idx = 0;

        for (int i = 0; i < haystack.length(); i++) {
            while (!(idx == 0 || haystack.charAt(i) == needle.charAt(idx))) {
                idx = lps[idx-1];
            }

            if (haystack.charAt(i) == needle.charAt(idx)) {
                if (idx == needle.length() - 1) {
                    return i - idx;
                }
                idx += 1;
            }
        }

        return -1;
    }
}